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 Exception
10     {
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             else
26             {
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                     else
75                     {
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 }