最短路径算法

 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 }