最短路问题（floyd算法）（优化待续）

问题描述：

最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

1.floyd算法

算法描述：

Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

时间复杂度：O（n^3）空间复杂度：O（n^2）

可以看下这篇文章，讲得非常清楚：http://blog.chinaunix.net/uid-26548237-id-3834873.html

下面就讲下我对这个算法的理解：

首先这个算法能做的事，就是寻找给定的加权图中多源点之间最短路径

也就是这张图：

这里有N个点，互相之间的路径长度不一，怎么求其中任意两点的最短路径。

floyd算法的思路就是从比较入手，比较两点直接连通和隔一个点连通的长度。

从v0开始，遍历任意两个点，寻找有没有两个点通过v0的最短路径比这两点直接连通的要短。

比如v0和v2，要比较这两个点直接连通和隔一个点连通的长度。从图上可知，v0-v2的最短路径是经过v1,走0-1-2，而不是直接0-2。所以结果是经过v1比直接连通要短。

再比如v0和v4，要比较这两个点直接连通和隔一个点连通的长度，但v0和v4没有直接连通怎么办，就设v0-v4直接连通的长度是无穷大，这样不管是经过v1还是经过v2，都比直接连通的长度要短。

找到后怎么办，就把最短的长度和路径结果保存起来，以此再遍历下一个点v1，继续比较。

全部遍历一遍后，就可以得到任意两点之间的最短路径了。

具体实现如下：

  1 #include <iostream>
  2 using namespace std;
  3 
  4 #define MAXVEX 20
  5 #define MAXEDGE 20
  6 #define INFINITY 65535
  7 
  8 
  9 
 10 typedef struct
 11 {
 12           int vexs[MAXVEX];
 13           int arc[MAXVEX][MAXVEX];
 14           int numVertexes,numEdges;
 15 }MGraph;
 16 
 17 typedef int Patharc[MAXVEX][MAXVEX];
 18 typedef int ShortPathTable[MAXVEX][MAXVEX];
 19 
 20 void CreateGraph(MGraph* G)
 21 {
 22           cout<<"请输入边数和顶点数:
";
 23           int d,n,i,j;
 24           cin>>d>>n;
 25           G->numVertexes = n;
 26           G->numEdges = d;
 27 
 28           //给顶点和边初始化
 29           for(i = 0;i<G->numVertexes;i++)
 30                     G->vexs[i] = i;
 31           for(i = 0;i<G->numVertexes;i++)
 32           {
 33                     for(j = 0;j<G->numVertexes;j++)
 34                     {
 35                               if(i==j)
 36                                         G->arc[i][j] = 0;
 37                               else
 38                                         G->arc[i][j] = G->arc[j][i] = INFINITY;
 39                     }
 40           }
 41 
 42           G->arc[0][1]=1;
 43           G->arc[0][2]=5;
 44           G->arc[1][2]=3;
 45           G->arc[1][3]=7;
 46           G->arc[1][4]=5;
 47 
 48           G->arc[2][4]=1;
 49           G->arc[2][5]=7;
 50           G->arc[3][4]=2;
 51           G->arc[3][6]=3;
 52           G->arc[4][5]=3;
 53 
 54           G->arc[4][6]=6;
 55           G->arc[4][7]=9;
 56           G->arc[5][7]=5;
 57           G->arc[6][7]=2;
 58           G->arc[6][8]=7;
 59 
 60           G->arc[7][8]=4;
 61 
 62           for(i = 0;i<G->numVertexes;i++)
 63           {
 64                     for(j = i;j<G->numVertexes;j++)
 65                     {
 66                               G->arc[j][i] = G->arc[i][j];
 67                     }
 68           }
 69 }
 70 
 71 /* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
 72 void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
 73 {
 74           int v,w,k;
 75           for(v = 0;v<G.numVertexes;v++)
 76           {
 77                     for(w = 0;w<G.numVertexes;w++)
 78                     {
 79                               (*P)[v][w] = w;
 80                                /* 初始化P */
 81                               (*D)[v][w] = G.arc[v][w];
 82                               /* D[v][w]值即为对应点间的权值 */
 83                     }
 84 
 85           }
 86           for(k = 0;k<G.numVertexes;k++)
 87           {
 88                     for(v = 0;v<G.numVertexes;v++)
 89                     {
 90                               for(w = 0;w<G.numVertexes;w++)
 91                               {
 92                                         if((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
 93                                         {
 94                                                   (*D)[v][w] = (*D)[v][k]+(*D)[k][w];
 95                                                   (*P)[v][w] = (*P)[v][k];
 96                                         }
 97 
 98                               }
 99 
100                     }
101           }
102 
103 }
104 
105 
106 int main()
107 {
108     int v,w,k=-1;
109 
110     MGraph G;
111 
112     Patharc P;
113     ShortPathTable D;
114 
115     CreateGraph(&G);
116 
117     ShortestPath_Floyd(G,&P,&D);
118 
119     cout<<"各区间最短路径如下：
";
120     for(v = 0;v<G.numVertexes;v++)
121     {
122               for(w = v+1;w<G.numVertexes;w++)
123               {
124                         cout<<"v"<<v<<"-v"<<w<<" weight: "<<D[v][w];
125                         k = P[v][w];
126                         cout<<" path: "<<v;
127                         while(k!=w)
128                         {
129                                   cout<<" -> "<<k;
130                                   k = P[k][w];
131                               }
132                               cout<<" -> "<<w<<" "<<endl;
133                     }
134                     cout<<endl;
135 
136           }
137 
138           cout<<"最短路径D
";
139 
140           for(v=0; v<G.numVertexes; ++v)
141           {
142                     for(w=0; w<G.numVertexes; ++w)
143                     {
144                               cout<<D[v][w]<<"  ";
145                     }
146                     cout<<endl;
147           }
148 
149           cout<<"最短路径P
";
150 
151           for(v=0; v<G.numVertexes; ++v)
152           {
153                     for(w=0; w<G.numVertexes; ++w)
154                     {
155                               cout<<P[v][w]<<"  ";
156                     }
157                     cout<<endl;
158           }
159 
160           return 0;
161 
162 
163 }

算法优化：

floyd(权值非负)适用于有向图和无向图

1 floyd 的思想就是通过枚举n个点利用DP的思想来更新最短距离的，假设当前枚举到第k个点，那么就有任意的两个点i , j ，如果i k 相连 j k 相连那么就可以知道这个时候dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);，那么只要枚举完n个点，那么就说明已经完全更新完所有两点直间的最短路。

2 floyd算法是最简单的最短路径的算法，可以计算图中任意两点间的最短路径。floyd算法的时间复杂度为o(n^3)，如果是一个没有边权的图，把相连的两点间的距离设为dis[i][j]=1.不相连的两点设为无穷大，用floyd算法可以判断i j两点是否相连。
3 floyd 算法不允许所有的权值为负的回路。可以求出任意两点之间的最短距离。处理的是无向图
4 缺点是时间复杂度比较高，不适合计算大量数据

5 如果dis[i][i] != 0，说明此时存在环。

6 如果利用floyd求最小值的时候，初始化dis为INF ，如果是求最大值的话初始化为-1.