Dijkstra算法求解最短路径分析

function Dijkstra(G, w, s)
   for each vertex v in V[G]         //初始化
         d[v] := infinity             // 將各點的已知最短距離先設成無窮大
         previous[v] := undefined     // 各点的已知最短路径上的前趋都未知
   d[s] := 0                         // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
   S := empty set
   Q := set of all vertices
   while Q is not an empty set       // Dijkstra演算法主體
         u := Extract_Min(Q)
         S.append(u)
         for each edge outgoing from u as (u,v)
                if d[v] > d[u] + w(u,v)       // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
                      d[v] := d[u] + w(u,v)   // 更新路径长度到更小的那个和值。
                      previous[v] := u        // 紀錄前趨頂點

public class Dijkstra
{
    public static final int M = -1;

    public static void main(String[] args)
    {
        int[][] map1 = { 
                { 0,  7,  9,  M,  M, 14 }, 
                { 7,  0,  10, 15, M, M },
                { 9,  10, 0,  11, M, 2 }, 
                { M,  15, 11, 0,  6, M },
                { M,  M,  M,  6,  0, 9 }, 
                { 14, M,  2,  M,  9, 0 } };

        int orig = 0;
        int[] shortPath = dijkstra_alg(map1, orig);

        if (shortPath == null)
        {
            return;
        }
        
        for (int i = 0; i < shortPath.length; i++)
        {
            System.out.println("从" + (orig + 1) + "出发到" + (i + 1) + "的最短距离为："
                    + shortPath[i]);
        }
    }

    public static int[] dijkstra_alg(int[][] weight, int orig)
    {
        int n = weight.length;              // 顶点个数

        int[] shortest = new int[n];        // 存放从start到其他各点的最短路径
        boolean[] visited = new boolean[n]; // 标记当前该顶点的最短路径是否已经求出，true表示已求出

        // 初始化，第一个顶点求出
        shortest[orig] = 0;
        visited[orig] = true;

        for (int count = 0; count != n - 1; count++) // 要加入n-1个顶点
        {
            // 选出一个距离初始顶点最近的未标记顶点
            int k = M;     
            int dmin = M;
            for (int i = 0; i < n; i++)
            {
                if (!visited[i] && weight[orig][i] != M)
                {
                     if (dmin == -1 || dmin > weight[orig][i])
                     {
                         dmin = weight[orig][i];
                         k = i;
                     }
                }
            }

            // 正确的图生成的矩阵不可能出现K == M的情况
            if (k == M)
            {
                System.out.println("the input map matrix is wrong!");
                return null;
            }
            
            shortest[k] = dmin;
            visited[k] = true;

            // 以k为中间点，修正从原点到未访问各点的距离
            for (int i = 0; i < n; i++)
            {
                if (!visited[i] && weight[k][i] != M)
                {
                    int callen = dmin + weight[k][i];
                    if (weight[orig][i] == M || weight[orig][i] > callen)
                    {
                        weight[orig][i] = callen;
                    }
                }
            }
        }

        return shortest;
    }
}