1 public class Dijkstra { 2   3     static final int maxWeight = 9999; 4       5     //distance保存了從起始節點到每一個節點的最短距離 6     //path保存了路徑 7     //v0是起始節點 8     public static void dijkstra(MyAdjGraphic g,int v0,int[] distance,int[] path) 9     throws Exception10     {11         int n = g.getNumOfVertice();//結點數量12         int[] s = new int[n]; //標示結點是否已被訪問的數組13         int minDis; //每次找到的最短路徑14         int u=0; //下一次最短路徑對應的結點的下標15          16         //初始化，把初始節點距離所有節點的信息初始化17         for(int i=0;i<n;i++)18         {19             distance[i] = g.getWeightOfEdges(v0, i);20             s[i] = 0; //未訪問21             if(i!=v0&&distance[i]<maxWeight)22             {23                 path[i]= v0;    24             }25             else26             {27                 path[i]=-1;28             }29         }30         s[0]=1; //標記為已訪問31          32         //下面是一個大循環，找出每個節點距離初始節點的最短距離33         for(int i=1;i<n;i++)34         {35             minDis = maxWeight;36              //從還未訪問過的節點中，選擇一個距起始節點最近的點37             for(int j=0;j<n;j++)38             {39                 if(distance[j]!=-1) //說明有邊存在40                 {41                     //結點未訪問，并且小于當前最小路徑42                     if(s[j]==0&&distance[j]<minDis)43                     {44                         u = j;45                         minDis = distance[j];46                     }47                 }48             }49             //如果節點都訪問到了，退出50             if(minDis==maxWeight)51             {52                 return ;53             }54              55             //把這個未訪問的節點設置為訪問過了56             s[u]=1;//標記為已訪問57              58             //然后以這個節點為主，進一步找最小的路徑與前面已有的路徑比較，取最小的。59             for(int j=0;j<n;j++)60             {61                 if(g.getWeightOfEdges(u, j)!=-1) //有邊存在62                 {63                     //說明起始節點還未能到達此節點64                     if(distance[j]==-1) //未訪問過65                     {66                         if(s[j]==0&&g.getWeightOfEdges(u, j)<maxWeight)67                         {68                             distance[j] = distance[u]+g.getWeightOfEdges(u, j);69                             //記錄找到的節點的前一個節點，記錄最小路徑70                             path[j]=u;71                         }72                     }73                     //若以前訪問過，則比較哪一條路徑比較短74                     else75                     {76                         //因為以前起始節點也路過這個，因此要把當前的路徑長度和以前的路徑長度進行比較77                         if(s[j]==0&&g.getWeightOfEdges(u, j)<maxWeight && distance[u]+g.getWeightOfEdges(u, j)<distance[j])78                         {79                             distance[j] = distance[u]+g.getWeightOfEdges(u, j);80                              //記錄找到的節點的前一個節點，記錄最小路徑81                             path[j]=u;82                         }83                     }84                 }85                 //一個大循環下來，distance里存放的是起始節點到目前能到達且未訪問節點的全部距離，86                   然后再用起初的循環找出距離最小的且未訪問的點作為主，進而繼續尋找87             }88                 89         }90          91     }92 }