public class ShortestPath_DIJ {
   private boolean[][] P;// v0到其余顶点的最短路径, 若P[v][w]为true，则w是从v0到v当前求得最短路径上的顶点
   private int[] D;// v0到其余顶点的带权长度
   public final static int INFINITY = Integer.MAX_VALUE;
   // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其权值D[v]
   public void DIJ(MGraph G, int v0) {
      int vexNum = G.getVexNum();
      P = new boolean[vexNum][vexNum];  // 用于记录经过的顶点
      D = new int[vexNum];        // 用于记录到达某顶点需要的最短路径和
      boolean[] finish = new boolean[vexNum];// finish[v]为true当且仅当v属于S,即已经求得从v0到v的最短路径
      // 数据初始化
      for (int v = 0; v < vexNum; v++) {
         finish[v] = false;
         D[v] = G.getArcs()[v0][v];   // D 记录v0到所有各个边的权值
         for (int w = 0; w < vexNum; w++)
            P[v][w] = false;      // 设空路径，及设置默认值
         if (D[v] < INFINITY) {
            P[v][v0] = true;      // 在P数组的第v行，标记v0被访问
            P[v][v] = true;       // 在P数组的第v行，标记邻接点被访问
         }
      }
      D[v0] = 0;// 初始化，v0顶点属于S集
      finish[v0] = true;
      int v = -1;
      // 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集
      for (int i = 1; i < vexNum; i++) {// 其余G.getVexNum-1个顶点
         int min = INFINITY;// 当前所知离v0顶点的最近距离
         for (int w = 0; w < vexNum; w++)
            if (!finish[w])
               if (D[w] < min) {
                  v = w;
                  min = D[w];
               }
         finish[v] = true;// 离v0顶点最近的v加入S集
         for (int w = 0; w < vexNum; w++)
            // 更新当前最短路径及距离
            if (!finish[w] && G.getArcs()[v][w] < INFINITY
                  && (min + G.getArcs()[v][w] < D[w])) { // 修改D[w]和P[w],w属于V-S
               D[w] = min + G.getArcs()[v][w];
               // w在v的基础上继续前行，所以将v经过的内容拷贝到w上
               System.arraycopy(P[v], 0, P[w], 0, P[v].length);
               P[w][w] = true;
            }
      }
   }
   public int[] getD() {
      return D;
   }
   public boolean[][] getP() {
      return P;
   }
   public static void main(String[] args) throws Exception {
      MGraph G = GenerateGraph.generateMGraph();
      ShortestPath_DIJ dij = new ShortestPath_DIJ();
      dij.DIJ(G, 0);
      dij.display(G);
   }
   // 用于输出最短路径上的各个顶点及权值
   public void display(MGraph G) throws Exception {
      if (D != null) {
         System.out.println("各个顶点到v0的最短路径上的点及最短距离分别是：");
         for (int i = 0; i < P.length; i++) {
            System.out.print("v0 - " + G.getVex(i) + ": ");
            for (int j = 0; j < P[i].length; j++) {
               if (P[i][j])
                  System.out.print(G.getVex(j) + "\t");
            }
            System.out.println("最短距离为： " + D[i]);
         }
      }
   }
}
// 调试结果：
// 各个顶点到v0的最短路径上的点及最短距离分别是：
// v0 - v0: v0 最短距离为： 0
// v0 - v1: v0 v1 最短距离为： 7
// v0 - v2: v0 v2 最短距离为： 1
// v0 - v3: v0 v3 最短距离为： 5
// v0 - v4: v0 v2 v4 最短距离为： 7
// v0 - v5: v0 v2 v5 最短距离为： 5

// k 表示在路径中新增的顶点号
// i 表示路径的源点
// j 表示路径的终点
if(D[i][k] + D[k][j] < D[i][j]) {
    D[i][j] = D[i][k] + D[k][j];    //更新最短路径长度
    P[i][j] = P[i][k] + P[k][j];    //更新最短路径
}

public class Example6_5_G9 {
  public final static int INFINITY = Integer.MAX_VALUE;
  public static void main(String[] args) throws Exception {
    Object vexs[] = { "v0", "v1", "v2" };
    int[][] arcs = { { 0, 4, 11},
            { 6, 0, 2},
            { 3, INFINITY,0}};
    MGraph G = new MGraph(GraphKind.DN, vexs.length, 5, vexs, arcs);
    ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
    floyd.FLOYD(G);
    display(floyd.getD());
  }
  // 输出各村的最短路径长度
  public static void display(int[][] D) {
    System.out.println("各顶点之间的最短路径长度为：");
    for (int v = 0; v < D.length; v++) {
      for (int w = 0; w < D.length; w++)
        System.out.print(D[v][w] + "\t");
      System.out.println();
    }
  }
}
// 调试结果：
//各顶点之间的最短路径长度为：
//    0 4 6
//    5 0 2
//    3 7 0