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