迪杰斯特拉算法

今天在学习数学建模的时候发现 matlab实现迪杰斯特拉算法太麻烦了 想来想去还是通过C语言或者JAVA语言来实现这个算法最划算。

算法特点：是来实现查看一个确定的点到其余各个顶点的最短路径问题。

算法思想

每次找到离源点最近的一个顶点，然后以该顶点为中心进行拓展，最终得到源点到其余各顶点的最短路径

重要的概念：松弛，即如果1->3为43，但是1->2->3为13，那么我们就用第二个距离来表示1->3的距离

算法步骤

• 将所有的顶点分为两个部分，一直最短路程的顶点集合P和未知最短路径的顶点集合Q。使用一个数组Book【】来记录那些点是在集合P中，book[i]=1表示已经在集合中了0表示不在
• 设置源点s到自己的最短距离为0，即dis[s]=0,如果存在源点能够直接到的点，则设置为e[ s ][ j ]如果不是则设为无穷大（9999）
• 在集合中找到一个离源点最近的顶点，加入到集合p，并考察以此点到其他的的边并进行松弛操作
• 循环第三步 知道全部的点都进入到我们的book数组中

算法实现

使用JAVA语言，代码中有注释说明用途

package com.dwx.passage2;

public class Dijkstar {
    public static void main(String[] args) {

        int[] dis = new int[10];
        int[] book = new int[10];
        int i,j,n,u = 0,v,min;
        int inf = 99999999;

        int e[][] = new int[][]{
                {0,2,1,8,inf,inf,inf,inf},
                {2,0,inf,6,1,inf,inf,inf},
                {1,inf,0,7,inf,inf,9,inf},
                {8,6,7,0,5,1,2,inf},
                {inf,1,inf,5,0,3,inf,9},
                {inf,inf,inf,1,3,0,4,6},
                {inf,inf,9,2,inf,4,0,3},
                {inf,inf,inf,inf,9,6,3,0}
        };
        n = e[0].length-1;



        //初始化dis数组  这里是记录源点到其他各点的最短距离的
        for (i=0;i<=n;i++){
            dis[i] = e[0][i];
        }

        //初始化book数组 book数组是记录已经被放入最短路径集合的点
        for (i=0;i<=n;i++){
            book[i] = 0;
        }
        //将第一个点（源点）放入book数组中
        book[0] = 1;
        //Dijkstra算法的核心
        for (i=0;i<=n-1;i++){
            min = inf;
            //找到距离源点最短的点
            for (j=0;j<=n;j++){
                if (book[j] == 0 && dis[j]<min){
                    min = dis[j];
                    u = j;
                }
            }
            //将这个点读到book数组中
            book[u] = 1;
            for (v=0;v<=n;v++){
                //收缩调整最短路径
                if (e[u][v] < inf){
                    if (dis[v]>dis[u]+e[u][v]){
                        dis[v] = dis[u]+e[u][v];
                    }
                }
            }

        }
        for (int di : dis) {
            System.out.print(di+"\t");
        }



    }


}

package com.dwx.passage2;

import java.util.Scanner;

public class Dijkstra {
    public static void main(String[] args) {
        int[][] e = new int[10][10];
        int[] dis = new int[10];
        int[] book = new int[10];
        int i,j,n,m,t1,t2,t3,u = 0,v,min;
        int inf = 99999999;


        //这个操作是在实现存储图
        //读入顶点个数 和 边的条数
        Scanner scanner = new Scanner(System.in);
        //n表示顶点个数 m表示边数
        n = scanner.nextInt();
        m = scanner.nextInt();

        //初始化 将自己到自己的顶点为0 其他的全改为inf
        for(i = 1;i <= n;i++){
            for (j = 1;j<=n;j++){
                if (i == j){
                    e[i][j] = 0;
                }else {
                    e[i][j] = inf;
                }

            }
        }


        //读入边和权值
        //这里我们使用的是有向边
        for (i = 1; i <= m;i++){
            //这里 t1表示起始的顶点 t2表示目标定点 t3表示权值
            t1 = scanner.nextInt();
            t2 = scanner.nextInt();
            t3 = scanner.nextInt();
            e[t1][t2] = t3;
            // e[t2][t1] = t3; //如果加上这一句话 就是在储存无向图
        }
        //初始化dis数组  这里是记录源点到其他各点的最短距离的
        for (i=1;i<=n;i++){
            dis[i] = e[1][i];
        }

        //初始化book数组 book数组是记录已经被放入最短路径集合的点
        for (i=1;i<=n;i++){
            book[i] = 0;
        }
        //将第一个点（源点）放入book数组中
        book[1] = 1;
        //Dijkstra算法的核心
        for (i=1;i<=n-1;i++){
            min = inf;
            //找到距离源点最短的点
            for (j=1;j<=n;j++){
                if (book[j] == 0 && dis[j]<min){
                    min = dis[j];
                    u = j;
                }
            }
            //将这个点读到book数组中
            book[u] = 1;
            for (v=1;v<=n;v++){
                //收缩调整最短路径
                if (e[u][v] < inf){
                    if (dis[v]>dis[u]+e[u][v]){
                        dis[v] = dis[u]+e[u][v];
                    }
                }
            }

        }
        for (int di : dis) {
            System.out.print(di+"\t");
        }



    }
}

**输入**
    6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 16
5 6 4

Donate