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

告别迷茫

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

 
 
 

日志

 
 

Floyd-Warshall 算法 两点之间的最短的路径的问题。  

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

  下载LOFTER 我的照片书  |
1.
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。 注意单独一条边的路径也不一定是最佳路径。编辑本段思想
  从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连。   对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。编辑本段实现
  Pascal程序:   for i:= 1 to n do   for j:= 1 to n do   read(f[i,j]);   for k:= 1 to n do   for i:= 1 to n do   for j:= 1 to n do   if (i<>j)and(i<>k)and(j<>k)and(f[i,k]+f[k,j]<f[i,j]) then   f[i,j]:=f[i,k]+f[k,j];编辑本段总评
  时间复杂度O(n^3),只要有存下邻接矩阵的空间,时间一般没问题,并且不必担心负权边的问题
2.路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用的是(松弛技术),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
状态转移方程

其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}
map[i,j]表示i到j的最短距离,K是穷举i,j的断点,map[n,n]初值应该为0,或者按照题目意思来做。
当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路
2算法过成
1,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i,j]=d,d表示该路的长度;否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j] = min( G[i,j], G[i,k]+G[k,j] ),如果G[i,j]的值变小,则D[i,j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
比如,要寻找从V5到V1的路径。根据D,假如D(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果D(5,3)=3,说明V5与V3直接相连,如果D(3,1)=1,说明V3与V1直接相连。
4.
在图论中经常会遇到这样的问题,在一个有向图里,求出任意两个节点之间的最短距离。当节点之间的权值是正值的时候,我们可以采用Dijkstra算法,用贪心策略加于解决。但当节点之间的权值有负数的时候,Dijkstra就行不通了,这里介绍另外一种算法——Floyd最短路径算法。
问题描述:
      如果有一个矩阵D=[d(ij)],其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通,那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序,通过这个距离矩阵D,把任意两个城市之间的最短路径找出来。
【分析】
       如何找出最短路径呢,这里需要用到动态规划的思想,对于任何一个城市而言,i 到 j 的最短距离不外乎存在经过 i 与 j 之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n是城市的数目),再检查d(ij)与d(ik)+d(kj)的值;在此d(ik)与d(kj)分别是目前为止所知道的 i 到 k 与 k 到 j 的最短距离,因此d(ik)+d(kj)就是 i 到 j 经过k的最短距离。所以,若有d(ij)>d(ik)+d(kj),就表示从 i 出发经过 k 再到j的距离要比原来的 i 到 j 距离短,自然把i到j的d(ij)重写为d(ik)+d(kj)<这里就是动态规划中的决策>,每当一个k查完了,d(ij)就是目前的 i 到 j 的最短距离。重复这一过程,最后当查完所有的k时,d(ij)里面存放的就是 i 到 j 之间的最短距离了<这就是动态规划中的记忆化搜索>。利用一个三重循环产生一个存储每个结点最短距离的矩阵.      
      用三个for循环把问题解决了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的枚举程序,但是仔细考虑的话,会发现是有问题的:
for i:=1 to n do
      for j:=1 to n do
            for k:=1 to n do
                   if.....
      问题出在我们太早的把i-k-j的距离确定下来了,假设一旦找到了i-p-j最短的距离后,i到j就相当处理完了,以后不会在改变了,一旦以后有使i到j的更短的距离时也不能再去更新了,所以结果一定是不对的。所以应当象下面一样来写程序:
for k:=1 to n do
      for i:=1 to n do
            for j:=1 to n do
                  if .....
      这样作的意义在于固定了k,把所有i到j而经过k的距离找出来,然后象开头所提到的那样进行比较和重写,因为k是在最外层的,所以会把所有的i到j都处理完后,才会移动到下一个K。

4.算法的实现

#define MAX_NAME 5 // 顶点字符串的最大长度+1
#define MAX_INFO 20 // 相关信息字符串的最大长度+1
typedef int VRType;
typedef char VertexType[MAX_NAME];
typedef char InfoType;
#include"c1.h"
#include"c7-1.h"
#include"bo7-1.cpp"
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

void ShortestPath_FLOYD(MGraph G,PathMatrix &P,DistancMatrix &D)
{ // 用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其
// 带权长度D[v][w]。若P[v][w][u]为TRUE,则u是从v到w当前求得最短
// 路径上的顶点。算法7.16
int u,v,w,i;
for(v=0;v<G.vexnum;v++) // 各对结点之间初始已知路径及距离
for(w=0;w<G.vexnum;w++)
{
D[v][w]=G.arcs[v][w].adj;
for(u=0;u<G.vexnum;u++)
P[v][w][u]=FALSE;
if(D[v][w]<INFINITY) // 从v到w有直接路径
{
P[v][w][v]=TRUE;
P[v][w][w]=TRUE;
}
}
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[v][u]+D[u][w]<D[v][w]) // 从v经u到w的一条路径更短
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;i++)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
}

void main()
{
MGraph g;
int i,j,k,l,m,n;
PathMatrix p;
DistancMatrix d;
CreateDN(g);
for(i=0;i<g.vexnum;i++)
g.arcs[i][i].adj=0; // ShortestPath_FLOYD()要求对角元素值为0
printf("邻接矩阵:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%11d",g.arcs[i][j]);
printf("\n");
}
ShortestPath_FLOYD(g,p,d);
printf("d矩阵:\n");
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
printf("%6d",d[i][j]);
printf("\n");
}
for(i=0;i<g.vexnum;i++)
for(j=0;j<g.vexnum;j++)
printf("%s到%s的最短距离为%d\n",g.vexs[i],g.vexs[j],d[i][j]);
printf("p矩阵:\n");
l=strlen(g.vexs[0]); // 顶点向量字符串的长度
for(i=0;i<g.vexnum;i++)
{
for(j=0;j<g.vexnum;j++)
{
if(i!=j)
{
m=0; // 占位空格
for(k=0;k<g.vexnum;k++)
if(p[i][j][k]==1)
printf("%s",g.vexs[k]);
else
m++;
for(n=0;n<m*l;n++) // 输出占位空格
printf(" ");
}
else
for(k=0;k<g.vexnum*l;k++) // 输出占位空格
printf(" ");
printf(" "); // 输出矩阵元素之间的间距
}
printf("\n");
}
}



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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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