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

luciferzf

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

1. void ShortestPath_Dijkstar(MGraph G,int VG,Pathare *P,ShortPathTable *D)
   
2. {
   
3.      int v,w,k,min;
   
4.      int final[MAX];
   
5. 
   
6.      for(v=0;v<G.numVertexes;v++)
   
7.      {
   
8.          final[v]=0;
   
9.          (*D)[v]=G.arc[v0][v];
   
10.          (*P)[v]=0;
    
11.      }
    
12.      (*D)[v0]=0;
    
13.      final[v0]=1;
    
14. 
    
15.      for(v=0;v<G.numVertexes;v++)
    
16.      {
    
17.          min=INFINTE;
    
18.          for(v=0;v<G.numVertexes;v++)
    
19.          {
    
20.              if(!final[w]&&(*D)[w]<min)
    
21.              {
    
22.                  k=w;
    
23.                  min=(*D)[w];
    
24.              }
    
25.          }
    
26.          final[k]=1;
    
27. 
    
28.          for(w=0;w<G.numVertexes;w++)
    
29.          {
    
30.              if(!final[w]&&(min+G.arc[k][w]<(*D)[w]))
    
31.              {
    
32.                  (*D)[w]=min+G.arc[k][w];
    
33.                  (*p)[w]=k;
    
34.              }
    
35.          }
    
36.      }
    
37. }

复制代码