[杂七杂八] 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("-----------------------");        }    }}

运行结果：