【算法设计与分析】最短路径的算法

winston

暂不讨论人工智能的启发式算法，那么最短路径算法主要有Dijkstra、Bellman-Ford、Floyd，前两者是单源最短路径，Floyd是全源最短路径，当然单源算法也可以通过枚举实现全源算法。而近来颇为流行的SPFA算法应该算是Bellman-Ford算法的队列实现，三者主要区别如下：

Dijkstra 算法的特点	每次选择的边一定是最终最短路径上的边	不允许出现负边	一般可以采用堆结构优化，邻接表或邻接矩阵都可以，但一般稠密图时才有利，倾向于邻接矩阵实现，代码量最大	o(n^2)其中n为顶点的数量，稠密图单源最短路径时有利
SPFA	每次进行一次松弛操作，用队列维护需松弛的顶点	可以有负边，但不能有负的回路	由于常用于稀松图，一般采用邻接表实现，代码量略小于Dijkstra	o(kE)，稀松图时单源，全源都有利
Floyd	每次选择一个顶点，尝试去松弛所有结点	可以有负边，但不能有负的回路	由于常用于稠密图，一般采用邻接矩阵实现，代码量最小	o(n^3)，稠密图全源路径时有利

最短路径中最为人熟知的应该是Dijkstra算法，该算法利用最短路径的性质每次都选择到一条最终路径中的边，是贪心解决问题的经典范例，各大教材中也论述最多。而SPFA算法由于其实现简单，效率优异，适用范围广泛，在各类算法比赛中越来越受重视。Floyd一直是全源最短路径的不二选择，只有近来才在稀松图的全源最短路径上受到SPFA的挑战。下面主要给出三个算法的实现，当然实现倾向于代码简洁和逻辑上的可记忆。
（1）Dijkstra直接给出最简单实现，优化实现就是在选择最小值的时候使用各种 堆 结构。void Dijkstra(int **G  ,int vexnum,

2.                   int *dist,int *path,)
3. {
4.         /*initiate*/
5.         bool *final = new bool[vexnum];
6.         for(int i=0; i<vexnum; ++i)
7.         {
8.                 final[i] = false;
9.                 dist[i] = G[0][i];
10.                 if(dist[i]<maxval)
11.                 {        path[i] = 0; }
12.                 else
13.                 {        path[i] = -1;}
14.         }
15.         /*visit*/
16.         final[0] = true;
19.         for(int i=1; i<vexnum; ++i)
20.         {
21.                 /*find min*/
22.                 int min = maxval;
23.                 int vex = -1;
24.                 for(int j=0; j<vexnum; ++j)
25.                         if(!final[j] && dist[j]<min)
26.                         {        min = dist[j]; vex = j; }
27.                
28.                 /*vist，加入连通分支点集*/
29.                 final[vex] = true;
30.                
31.                 /*update*/
32.                 for(int k=0; k<vexnum; ++k)
33.                         if(!final[k] && G[vex][k]<maxval)        /*如果k顶点需要松弛，且连接在vex上*/
34.                                 if(dist[vex]+G[vex][k]<dist[k])  /*如果能够利用vex顶点松弛 k 顶点  */
35.                                 {
36.                                         dist[k] = dist[vex]+G[vex][k];
37.                                         path[k] = vex;
38.                                 }
39.         }
40. }

复制代码

整个算法的框架就是：
     初始化 辅助数组
     做n-1次
            寻找当前连通分支的最小代价邻接点
            更新辅助数组（松弛操作）


（2）Floyd算法就给出那个经典的 k , i , j版本了const int vexnum = 5;

2. const int maxval = 65536;/*图中表示不可达的长度*/
3. void Floyd(int G[][vexnum],int dist[][vexnum],int path[][vexnum])
4. {
6.         for(int i=0; i<vexnum; ++i)
7.                 for(int j=0; j<vexnum; ++j)
8.                 {
9.                         /*initiate the dist[][] and path[][]*/
10.                         dist[i][j] = G[i][j];
11.                         if(i!=j && dist[i][j]<maxval)
12.                         {        path[i][j] = i;}
13.                         else
14.                         {        path[i][j] = -1;}
15.                 }
16.        
18.         for(int k=0; k<vexnum; ++k)
19.                 for(int i=0; i<vexnum; ++i)
20.                         for(int j=0; j<vexnum; ++j)
21.                                 if( dist[i][j] > dist[i][k]+dist[k][j] )/*如果可以用k顶点松弛 i j之间的通路*/
22.                                 {
23.                                         dist[i][j] = dist[i][k] + dist[k][j];
24.                                         path[i][j] = path[k][j];
25.                                 }
26. }

复制代码

算法框架清晰直接：
    初始化操作
    k , i ,j 三种循环
        如果 [ i ][ j ]之间可以用[ k ]松弛，那么执行松弛


（3）SPFA直接给出一个SLF优化的实现，如果不优化可以略简洁一些。#include <deque>

2. using namespace std;
4. const int maxval = 0x7F7F7F7F7F;
6. struct Edge          /*多用于稀松图，所以采用邻接表实现*/
7. {   
8.         int dest;
9.         int cost;
10.         Edge* next;
11. };
13. void SPFA(Edge* G[] ,int vexnum,
14.               int dist[],int path[])
15. {
16.         /* initilise */
17.         for(int i=0; i<vexnum; ++i)
18.         {        dist[i] = maxval;  path[i] = -1;}
19.         dist[0] = 0;             /*源点已经到达*/
20.        
21.        
22.         deque<int> Q;             /*双向队列维持顶点的队列*/
23.         Q.push_back(0);           /*源点入队*/
24.         bool inQueue[maxedg] = {};/*标示顶点是否已经在队列中*/
25.         inQueue[0] = true;        /*源点入队标记*/
26.        
27.        
28.         /*开始循环松弛*/
29.         while(!Q.empty())
30.         {
31.                 int cur = Q.front();     /*取出队首顶点*/
32.                 Q.pop_front();
33.                 inQueue[cur]=false;      /*队列操作始终和inQueue[]标记同步*/
35.                 for(Edge *p=G[cur]; p!=NULL; p=p->next )/*遍历队首关联的顶点*/
36.                 {
37.                         int pv = p->dest;  /*p关联的顶点*/
38.                         if(dist[cur]+p->cost < dist[pv])/*如果可松弛*/
39.                         {
40.                                 dist[pv] = dist[cur]+p->cost;
41.                                 path[pv] = cur;
43.                                 if(!inQueue[pv])             /*如果可入队*/
44.                                 {       
45.                                         if(!Q.empty()&&dist[pv]<dist[Q.front()])/*如果距离小于队首*/
46.                                         {        Q.push_front(pv);}
47.                                         else
48.                                         {        Q.push_back(pv); }
49.                                        
50.                                         inQueue[pv] = true;        /*入队标记*/
51.                                 }
52.                         }
53.                 }
54.         }
55. }

复制代码

使用了STL的<deque>，算法框架是：
   初始化 辅助数组
   源点入队
   如果队不空，取队首元素，进行松弛操作，被松弛的顶点不在队中则 入队

作者：theprinceofelf 发表于2012-2-2 22:21:28 原文链接