DijKstra算法实现图的最短路径

这个图的构造使用矩阵构造出的,与之前邻接表不同

下面是此算法的思路http://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html参考

public class Dijkstra {
     
    private static int N = 1000;
    private static int[][] Graph = {
            { 0, 1, 5, N, N, N, N, N, N },
            { 1, 0, 3, 7, 5, N, N, N, N },
            { 5, 3, 0, N, 1, 7, N, N, N },
            { N, 7, N, 0, 2, N, 3, N, N },
            { N, 5, 1, 2, 0, 3, 6, 9, N },
            { N, N, 7, N, 3, 0, N, 5, N },
            { N, N, N, 3, 6, N, 0, 2, 7 },
            { N, N, N, N, 9, 5, 2, 0, 4 },
            { N, N, N, N, N, N, 7, 4, 0 } };
 
    public static void main(String[] args) {
        dijkstra(0, Graph);
    }
 
    /**
     * Dijkstra最短路径。
     * 即图中"节点vs"到其它各个节点的最短路径。
     * @param vs 起始节点
     * @param Graph 图
     */
    public static void dijkstra(int vs, int[][] Graph) {
        int n = Graph.length;
        // 前驱节点数组
        int prenode[] = new int[n];
        //最短路径的数组
        int mindisk[] = new int [n];
        //判断是否找到了最短路径
        boolean find[] = new boolean[n];
        
        for(int i=0;i<n;i++){
            prenode[i] = i;
            mindisk[i] = Graph[vs][i];
            find[i] = false;
        }
        int vnode = 0;
        find[vs] = true;
        
        for(int k=1;k<Graph.length;k++){
            int min=N;
            for(int j=0;j<Graph.length;j++){
                if(!find[j]&&min>mindisk[j]){
                    min = mindisk[j];
                    vnode = j;
                }
            }
            find[vnode] = true;
            for(int j=0;j<Graph.length;j++){
                if(!find[j]&&(min+Graph[vnode][j])<mindisk[j]){
                    mindisk[j] = min+Graph[vnode][j];
                    prenode[j] = vnode;//
                }
            }
        }
        for(int i=0;i<n;i++){
            System.out.print("V"+vs+"到达"+"V"+i+"的最短距离S是:"+mindisk[i]);
            System.out.println("("+"V"+prenode[i]+"->"+"V"+i+")");
        }
    }
}

V0到达V0的最短距离S是:0(V0->V0)
V0到达V1的最短距离S是:1(V1->V1)
V0到达V2的最短距离S是:4(V1->V2)
V0到达V3的最短距离S是:7(V4->V3)
V0到达V4的最短距离S是:5(V2->V4)
V0到达V5的最短距离S是:8(V4->V5)
V0到达V6的最短距离S是:10(V3->V6)
V0到达V7的最短距离S是:12(V6->V7)
V0到达V8的最短距离S是:16(V7->V8)