《数据结构与算法》——最小路径

luciferzf

最短路径：
1）迪杰斯特拉算法：以贪心算法为核心，分为三部分，用三个数组P,D,FINAL分别储存路径长度，各个定点的前驱定点，各个定点的遍历情况。
首先，进行初始化，P[0]=0，D[0]=0，FINAL[0]=1;
然后进行循环，找到当前定点i相邻定点的最短边l，将p[i-1]+l赋值给p[i]；
再循环D数组，如果发现经过i点的更短路径，则更新p[i]的值，并修改FINAL的值。
重复三个步骤直至遍历完终点定点。
2）弗洛伊德算法：比起迪杰斯特拉算法，弗洛伊德算法时间复杂度要更高，因为弗洛伊德算法计算的是所有点的最小路径。
算法相比，弗洛伊德算法要比迪杰斯特拉算法多一个循环，用以遍历每个定点到其他定点的最小路径必须经过的定点

void ShortestPath_Dijkstar(MGraph G,int VG,Pathare *P,ShortPathTable *D)
 {
     int v,w,k,min;
     int final[MAX];

     for(v=0;v<G.numVertexes;v++)
     {
         final[v]=0;
         (*D)[v]=G.arc[v0][v];
         (*P)[v]=0;
     }
     (*D)[v0]=0;
     final[v0]=1;

     for(v=0;v<G.numVertexes;v++)
     {
         min=INFINTE;
         for(v=0;v<G.numVertexes;v++)
         {
             if(!final[w]&&(*D)[w]<min)
             {
                 k=w;
                 min=(*D)[w];
             }
         }
         final[k]=1;

         for(w=0;w<G.numVertexes;w++)
         {
             if(!final[w]&&(min+G.arc[k][w]<(*D)[w]))
             {
                 (*D)[w]=min+G.arc[k][w];
                 (*p)[w]=k;
             }
         }
     }
 }