最短路径算法

1publicclassDijkstra {23staticfinalintmaxWeight = 9999;45//distance保存了从起始节点到每一个节点的最短距离6//path保存了路径7//v0是起始节点8publicstaticvoiddijkstra(MyAdjGraphic g,intv0,int[] distance,int[] path)9throwsException10{11intn = g.getNumOfVertice();//结点数量12int[] s =newint[n];//标示结点是否已被访问的数组13intminDis;//每次找到的最短路径14intu=0;//下一次最短路径对应的结点的下标1516//初始化，把初始节点距离所有节点的信息初始化17for(inti=0;i<n;i++)18{19distance[i] =g.getWeightOfEdges(v0, i);20s[i] = 0;//未访问21if(i!=v0&&distance[i]<maxWeight)22{23path[i]=v0;24}25else26{27path[i]=-1;28}29}30s[0]=1;//标记为已访问3132//下面是一个大循环，找出每个节点距离初始节点的最短距离33for(inti=1;i<n;i++)34{35minDis =maxWeight;36//从还未访问过的节点中，选择一个距起始节点最近的点37for(intj=0;j<n;j++)38{39if(distance[j]!=-1)//说明有边存在40{41//结点未访问，并且小于当前最小路径42if(s[j]==0&&distance[j]<minDis)43{44u =j;45minDis =distance[j];46}47}48}49//如果节点都访问到了，退出50if(minDis==maxWeight)51{52return;53}5455//把这个未访问的节点设置为访问过了56s[u]=1;//标记为已访问5758//然后以这个节点为主，进一步找最小的路径与前面已有的路径比较，取最小的。59for(intj=0;j<n;j++)60{61if(g.getWeightOfEdges(u, j)!=-1)//有边存在62{63//说明起始节点还未能到达此节点64if(distance[j]==-1)//未访问过65{66if(s[j]==0&&g.getWeightOfEdges(u, j)<maxWeight)67{68distance[j] = distance[u]+g.getWeightOfEdges(u, j);69//记录找到的节点的前一个节点，记录最小路径70path[j]=u;71}72}73//若以前访问过，则比较哪一条路径比较短74else75{76//因为以前起始节点也路过这个，因此要把当前的路径长度和以前的路径长度进行比较77if(s[j]==0&&g.getWeightOfEdges(u, j)<maxWeight && distance[u]+g.getWeightOfEdges(u, j)<distance[j])78{79distance[j] = distance[u]+g.getWeightOfEdges(u, j);80//记录找到的节点的前一个节点，记录最小路径81path[j]=u;82}83}84}85//一个大循环下来，distance里存放的是起始节点到目前能到达且未访问节点的全部距离，86然后再用起初的循环找出距离最小的且未访问的点作为主，进而继续寻找87}8889}9091}92}