注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

【转载】最短路径算法—Floyd-Warshall算法分析与实现  

2014-12-04 23:27:39|  分类: 数据结构---严老 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Floyd-Warshall算法,简称Floyd算法,用于求解任意两点间的最短距离时间复杂度为O(n^3)
使用条件&适用范围
    通常可以在任何图中使用,包括有向图、带负权边的图、稠密图效果最佳(对于稠密图,效率要高于执行|V|次Dijkstar算法)。
    Floyd-Warshall算法用来找出每对点之间的最短距离。他需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。

    1、注意单独一条边的路径也不一定是最佳路径。
    2、从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有变相连。
       对于每一对顶点 u 和 v ,看看是否存在一个顶点 w 是的从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
    3、不可思议的是,只要安排适当,就能得到结果。
伪代码:
//dist(i,j)为从节点 i 到节点 j 的最短距离
//初始化:dist(i,j) = weight(i,j)
For i←1 to n do
   For j←1 to n do
      dist(i,j) = weight(i,j)
For k←1 to n do //k为“媒介节点”
   For i←1 to n do
      For j←1 to n do
         if(dist(i,k) + dist(k,j) < dist(i,j)) then  //是否是更短的路径?
             dist(i,j) = dist(i,k) + dist(k,j)
dist即为所有点对的最短路径矩阵。

我们平时所见的Floyd算法的一般形式如下:

1 void Floyd()   {
2     int i,j,k;
3     for(k=1;k<=n;k++)
4         for(i=1;i<=n;i++)
5             for(j=1;j<=n;j++)
6                 if(dist[i][k]+dist[k][j]<dist[i][j])
7                     dist[i][j]=dist[i][k]+dist[k][j];
8 }

          注意下第6行这个地方,如果dist[i][k]或者dist[k][j]不存在,程序中用一个很大的数代替。最好写成if(dist[i][k]!=INF && dist[k][j]!=INF && dist[i][k]+dist[k][j]<dist[i][j]),从而防止溢出所造成的错误。

     Floyd算法的实现以及输出最短路径和最短路径长度,具体过程请看【动态演示Floyd算法】


代码说明几点:

    1、A[][]数组初始化为各顶点见的原本距离,最后存储各顶点间的最短距离。

    2、path[][]数组保存最短路径,与当前迭代次数有关。初始化都为-1,表示没有中间顶点。在求A[i][j]过程中,path[i][j]存放从顶点vi到顶点vj的中间顶点编号不大于k的最短路径上前一个结点的编号。在算法结束时,由二维数组path的值回溯,可以得到从顶点vi到顶点vj的最短路径。

    初始化A[][]数组为如下,即有向图的邻接矩阵。

    完整代码如下:

#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;
#define MaxVertexNum 100
#define INF 32767
typedef struct
{
char vertex[MaxVertexNum];
int edges[MaxVertexNum][MaxVertexNum];
int n,e;
}MGraph;
void CreateMGraph(MGraph &G)
{
int i,j,k,p;
cout << "请输入顶点数和边数:";
cin >> G.n >> G.e;
cout << "请输入顶点元素:";
for(i = 0;i < G.n;i++)
cin >> G.vertex[i];
for(i = 0;i < G.n;i++)
for(j = 0;j < G.n;j++)
{
G.edges[i][j] = INF;
if(i == j)
G.edges[i][j] = 0;
}
for(k = 0;k < G.e;k++)
{
cout << "请输入第" << k+1 << "条弧头弧尾序号和相应的权值:";
cin >> i >> j >> p;
G.edges[i][j] = p;
}
}
void Ppath(int path[][MaxVertexNum],int i,int j)
{
int k;
k = path[i][j];
if (k == -1)
return;
Ppath(path,i,k);
printf("%d,",k);
Ppath(path,k,j);
}
void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n)
{
int i,j;
for(i = 0;i < n;i++)
for(j = 0;j < n;j++)
{
if(A[i][j] == INF)
{
if(i != j)
printf("从%d到%d没有路径\n",i,j);
}
else
{
printf("从%d到%d=>路径长度:%d 路径:",i,j,A[i][j]);
printf("%d,",i);
Ppath(path,i,j);
printf("%d\n",j);
}
}
}
void Floyd(MGraph G)
{
int i,j,k;
int A[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];
for(i = 0;i < G.n;i++)
for(j = 0;j < G.n;j++)
{
A[i][j] = G.edges[i][j];
path[i][j] = -1;
}
for(k = 0;k < G.n;k++)
for(i = 0;i < G.n;i++)
for(j = 0;j < G.n;j++)
if(A[i][j] > A[i][k] + A[k][j])
{
A[i][j] = A[i][k] + A[k][j];
path[i][j] = k;
}
Dispath(A,path,G.n);
}
int main()
{
MGraph G;
CreateMGraph(G);
Floyd(G);
return 0;
}

Input:

最短路径算法—Floyd-Warshall算法分析与实现 - 瘋子 - 瘋子

Output:

最短路径算法—Floyd-Warshall算法分析与实现 - 瘋子 - 瘋子


     上面这个形式的算法其实是Floyd算法的精简版,而真正的Floyd算法是一种基于DP(Dynamic Programming)的最短路径算法

         设图G个顶点的编号为1n。令c [i, j, k]表示从的最短路径的长度,其中表示该路径中的最大顶点,也就是说c[i,j,k]这条最短路径所通过的中间顶点最大不超过k。因此,如果G中包含边<i, j>,则c[i, j, 0] =<i, j> 的长度;若i= j ,则c[i,j,0]=0;如果G中不包含边<i, j>,则c (i, j, 0)= +∞c[i, j, n] 则是从的最短路径的长度。
          对于任意的k>0,通过分析可以得到:中间顶点不超过的最短路径有两种可能:该路径含或不含中间顶点k若不含,则该路径长度应为c[i, j, k-1],否则长度为 c[i, k, k-1] +c [k, j, k-1]c[i, j, k]可取两者中的最小值。
         状态转移方程:c[i, j, k]=min{c[i, j, k-1], c [i, k, k-1]+c [k, j, k-1]}k0

         这样,问题便具有了最优子结构性质,可以用动态规划方法来求解。

         为了进一步理解,观察上面这个有向图:若k=0, 1, 2, 3,则c[1,3,k]= +∞c[1,3,4]= 28;若k = 5, 6, 7,则c [1,3,k] = 10;若k=8, 9, 10,则c[1,3,k] = 9。因此13的最短路径长度为9
         下面通过程序来分析这一DP过程,对应上面给出的有向图:

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int INF = 100000;
 5 int n=10,map[11][11],dist[11][11][11];
 6 void init(){
 7     int i,j;
 8     for(i=1;i<=n;i++)
 9         for(j=1;j<=n;j++)
10             map[i][j]=(i==j)?0:INF;
11     map[1][2]=2,map[1][4]=20,map[2][5]=1;
12     map[3][1]=3,map[4][3]=8,map[4][6]=6;
13     map[4][7]=4,map[5][3]=7,map[5][8]=3;
14     map[6][3]=1,map[7][8]=1,map[8][6]=2;
15     map[8][10]=2,map[9][7]=2,map[10][9]=1;
16 }
17 void floyd_dp(){
18     int i,j,k;
19     for(i=1;i<=n;i++)
20         for(j=1;j<=n;j++)
21             dist[i][j][0]=map[i][j];
22     for(k=1;k<=n;k++)
23         for(i=1;i<=n;i++)
24             for(j=1;j<=n;j++){
25                 dist[i][j][k]=dist[i][j][k-1];
26                 if(dist[i][k][k-1]+dist[k][j][k-1]<dist[i][j][k])
27                     dist[i][j][k]=dist[i][k][k-1]+dist[k][j][k-1];
28             }
29 }
30 int main(){
31     int k,u,v;
32     init();
33     floyd_dp();
34     while(cin>>u>>v,u||v){
35         for(k=0;k<=n;k++){
36             if(dist[u][v][k]==INF) cout<<"+∞"<<endl;
37             else cout<<dist[u][v][k]<<endl;
38         }
39     }
40     return 0;
41 }

  输入 1 3
  
输出 +∞
            +∞
            +∞
            +∞
            28
            10
            10
            10
            9
            9
            9


           Floyd-Warshall算法不仅能求出任意2点间的最短路径还可以保存最短路径上经过的节点。下面用精简版的Floyd算法实现这一过程,程序中的图依然对应上面的有向图。

 1 #include <iostream>
 2 using namespace std;
 
 4 const int INF = 100000;
 5 int n=10,path[11][11],dist[11][11],map[11][11];
 6 void init(){
 7     int i,j;
 8     for(i=1;i<=n;i++)
 9         for(j=1;j<=n;j++)
10             map[i][j]=(i==j)?0:INF;
11     map[1][2]=2,map[1][4]=20,map[2][5]=1;
12     map[3][1]=3,map[4][3]=8,map[4][6]=6;
13     map[4][7]=4,map[5][3]=7,map[5][8]=3;
14     map[6][3]=1,map[7][8]=1,map[8][6]=2;
15     map[8][10]=2,map[9][7]=2,map[10][9]=1;
16 }
17 void floyd(){
18     int i,j,k;
19     for(i=1;i<=n;i++)
20         for(j=1;j<=n;j++)
21             dist[i][j]=map[i][j],path[i][j]=0;
22     for(k=1;k<=n;k++)
23         for(i=1;i<=n;i++)
24             for(j=1;j<=n;j++)
25                 if(dist[i][k]+dist[k][j]<dist[i][j])
26                     dist[i][j]=dist[i][k]+dist[k][j],path[i][j]=k;
27 }
28 void output(int i,int j){
29     if(i==j) return;
30     if(path[i][j]==0) cout<<j<<' ';
31     else{
32         output(i,path[i][j]);
33         output(path[i][j],j);
34     }
35 }
36 int main(){
37     int u,v;
38     init();
39     floyd();
40     while(cin>>u>>v,u||v){
41         if(dist[u][v]==INF) cout<<"No path"<<endl;
42         else{
43             cout<<u<<' ';
44             output(u,v);
45             cout<<endl;
46         }
47     }
48     return 0;
49 }

  输入 1 3                    
  
输出 1 2 5 8 6 3

  评论这张
 
阅读(12)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017