你的位置:首页 > Java教程

[Java教程]最短路径算法


 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 }