1. public class DijkstraSP {
    2.     //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的倒数第二个顶点
    3.     private int[] edgeTo;
    4.     //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    5.     private double[] distValue;
    6.     //是否做了标记，加入树中
    7.     private boolean[] marked;
    9.     //构造方法
    10.     //根据一副加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
    11.     public DijkstraSP(EdgeWeightedDigraph G, int topPoint) {
    12.         int pointNum = G.V();
    13.         System.out.println("pointNum: "+pointNum);
    14.         if (topPoint>pointNum-1){
    15.             throw new Error("超出范围");
    16.         }
    18.         //创建一个和图的顶点数一样大小数组，表示从顶点s到当前顶点的最短路径上的倒数第二个顶点
    19.         this.edgeTo = new int[pointNum];
    20.         Arrays.fill(edgeTo, -1); //初始化都没有，除了顶点
    21.         edgeTo[topPoint] = topPoint;
    24.         //创建一个和图的顶点数一样大小的double数组，表示权重，并且初始化数组中的内容为无穷大，无穷大即表示不存在这样的边
    25.         this.distValue = new double[pointNum];
    26.         Arrays.fill(distValue, Double.POSITIVE_INFINITY);
    27.         distValue[topPoint] = 0.0; //到顶点自身的距离了为0
    29.         //marked初始化
    30.         this.marked = new boolean[G.V()];
    31.         int minPoint = 0;
    32.         for (int i = (topPoint + 1) % pointNum; i != topPoint; i = (i + 1) % pointNum) {
    33.             double minDist = Double.POSITIVE_INFINITY;//每次要重置最小值
    34.             //求出 distValue中最短的路径，即最小值
    35.             for (int j = 0; j < pointNum; j++) {
    36.                 if (!marked[j]&&distValue[j]<minDist){
    37.                     minDist = distValue[j];
    38.                     minPoint = j;
    39.                 }
    40.             }
    41.             if (minDist == Double.POSITIVE_INFINITY){
    42.                 break;
    43.             }
    44.             marked[minPoint] = true;//将点加入树，标记
    45.             //遍历他的邻接表，更新distValue，更新邻接表中顶点的上一个顶点为该顶点
    46.             for (DirectedEdge e : G.adj(minPoint)){
    47.                 //获取边e的终点
    48.                 int w = e.to();
    49.                 if (!marked[w]&&minDist + e.weight()<distValue[w]){
    50.                     distValue[w] = minDist + e.weight();
    51.                     edgeTo[w] = minPoint;
    52.                 }
    53.             }
    54.         }
    56.     }
    57.     public double[] getDistValue(){
    58.         return distValue;
    59.     }
    61.     public int[] getEdgeTo(){
    62.         return edgeTo;
    63.     }
    65.     public boolean[] getMarked(){
    66.         return marked;
    67.     }
    69.     //判断从顶点s到顶点v是否可达
    70.     public boolean hasPathTo(int v){
    71.         return distValue[v]<Double.POSITIVE_INFINITY;
    72.     }
    73. }