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 = Dijsktra(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[] Dijsktra(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;
        }
    }