Java 实现 Dijsktra 算法

看看书中的描述：

书中是用C++实现的，C++比较难，懂个思路就行，这里用java实现：

package graph;

public class Dijkstra {

private static final int MAXSIZE = 1000;
private static final int INF = 1200;
private static final int N = 6;

public static void main(String[] args) {
        System.out.println("------------Dijsktra------------");
int[][] data = {
                {MAXSIZE, 12, MAXSIZE, 12, 5, MAXSIZE},
                {MAXSIZE, MAXSIZE, 7, MAXSIZE, 4, MAXSIZE},
                {MAXSIZE, MAXSIZE, MAXSIZE,  MAXSIZE, MAXSIZE, 1},
                {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, 7},
                {MAXSIZE, MAXSIZE, 14, 9, MAXSIZE, 32},
                {MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE, MAXSIZE},
        };
int v = 1;
        System.out.println("打印有向图的邻接矩阵：");
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
                System.out.print(" " + data[i][j]);
            }
            System.out.println();
        }
        System.out.println("打印原点1到其它各点的最短路径及其长度：");
        toDijsktra(data, v);
    }

private static void toDijsktra(int[][] data, int v) {
//dist[]顶点到顶点的最短距离
int[] dist = new int[N];
//path[]存放上一个顶点
int[] path = new int[N];
//s[]存放已经加入到最短路径的顶点
int[] s = new int[N];
int f = v - 1;
//初始化第一个顶点
for(int i = 0; i < N; i++) {
            dist[i] = data[f][i];
if(dist[i] != MAXSIZE) {
                path[i] = v;
            }
else {
                path[i] = 0;
            }
        }
for(int i = 0; i < N; i++) {
            s[i] = 0;
        }
//将第一个顶点加入最短路径集合
        s[f] = 1;
//第一个顶点到第一个顶点的距离为0
        dist[f] = 0;
int k = 0;
for(int i = 0; i < N - 1; i++) {
int min = INF;
//该for循环找出最短的边
for(int j = 0; j < N; j++) {
if((s[j] == 0) && (dist[j] < min)) {
                    min = dist[j];
//最短边的顶点赋给K
                    k = j;
                }
            }
//将K顶点加入最短路径集合
            s[k] = 1;
//更新d[]的值，保证d[j]里面的值是有第一个顶点到k顶点的最短距离
for(int j = 0; j < N; j++) {
if((s[j] == 0) && (dist[j] > (dist[k] + data[k][j]))) {
                    dist[j] = dist[k] + data[k][j];
                    path[j] = k + 1;
                }
            }
        }
for(int i = 0; i < N; i++) {
            System.out.print(v + "到"  + (i+1) + "的最短距离是");
            System.out.print(dist[i]);
            System.out.println();
int pre = path[i];
            System.out.print("路径:" + (i+1));
while(pre != 0) {
                System.out.print("<------" + pre);
                pre = path[pre-1];
            }
            System.out.println();
            System.out.println("-----------------------");
        }
    }
}

运行结果：