图论之最短路径算法

浏览数：27 / 时间：2015年06月08日

dijkstra算法

　　　　基本思想：某最短路径上的点与源点之间的最短路径必然也在改最短路径之上，采用贪心策略，每次选取当前最短路径即可。

 1 void dijkstra(int n)
 2 {
 3     int num=1,i;
 4     int min,pos;
 5     vis[n]=1;
 6 
 7     while(num<n)//n-1次循环
 8     {
 9         min=MaxInt;
10         for(i=1; i<n; i++)
11             if(vis[i]==0 && dis[i]<min)
12             {
13                 pos=i;
14                 min=dis[i];
15             }
16         vis[pos]=1;
17         dis[pos]=min;
18 
19         for(i=1; i<n; i++)
20             if(vis[i]==0 && dis[i]>dis[pos]+map[pos][i])
21                 dis[i]=min+map[pos][i];//更新权值
22 
23         num++;
24     }
25 }

floyd算法

　　　　基本思想：采用动态规划思想，点i，j之间的最短路径要么包含点k，要么不包含点k，选择最小的即可。

 1 void floyd(int n)
 2 {
 3     int i,j,k;
 4     memset(dis,MaxInt,sizeof(dis));
 5 
 6     for(i=1; i<=n; i++)
 7         for(j=1; j<=n; j++)
 8             for(k=1; k<=n; k++)
 9                 if(dis[i][j] > dis[i][k]+dis[k][j] )
10                     dis[i][j] = dis[i][k]+dis[k][j];
11 }

spfa算法

　　　　基本思想：spfa算法是bellman-ford算法的队列实现，用dis数组表示点与源点之间的当前最短距离，用数组vis标记点是否在队列中，初始只有源点在队列中，每次取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有的最短距离都确定下来，结束算法。若一个点入队次数超过n，则有负权环。

 1 void spfa(int n)
 2 {
 3     int i,temp;
 4 
 5     dis[n]=0;
 6     vis[n]=1;
 7     queue<int> Q;
 8     Q.push(n);
 9 
10     while(!Q.empty())
11     {
12         temp=Q.front(); Q.pop();
13 
14         for(i=1; i<n;i++)
15             if(dis[i]>dis[temp]+map[temp][i])
16             {
17                 dis[i]=dis[temp]+map[temp][i];
18                 if(!vis[i])
19                 {
20                     Q.push(i);
21                     vis[i]=1;
22                 }
23             }
24         vis[temp]=0;
25     }
26 }