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

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

最短路径问题  

2009-07-11 21:47:19|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

求最短路径的主要算法有三种,分别是Dijkstra,Floyd和Bellman-Ford。它们的介绍如下

1.Dijstra算法

解决的问题:主要用于求解非负权的单源最短路径。

算法的思想:从源点开始每次合并距离源点所在集合最近的点到源点集合,距离用dis数组记录,合并后应用松弛原理更新dis数组的值,直到所有的点都在源点集合,或者发现图不连通。关键是判断dis[k]+map[k] [j]和dis[j]的大小,即判断从源点经过k点再到j点的距离是否比之前得出的到j点的距离要小,如果是就更新dis[j]。作为Dijkstra的一个关键结果是从源点s到v的一条最短路径是这条单边路径(s,v)的话,我们可以立刻将节点v加到源点集合中。如果没有负边,显然路径(s,v)是到v最短的,因为任何其他从s到v的路径必须从一条从s出发的边开始,这条边至少和边(s,v)的权一样大。下面解释一下为什么Dijstra不能用于负权边,我们可以从一条权值较大的边开始,然后接着用负权的边进行补偿,它比从一条权值小的边开始的路径更小,所以Dijstra的贪心方法在有负权边的情况下是不适用的。

代码如下(省去了一些变量的定义):

void DIJ_ShortestPath(int src,int n){
    int i;
    int index,min;
    for(i=1;i<=n;i++){
        dis[i]=map[src] [i];    //初始化源点到各个点的距离
    }
    used[src]=true;          //将源点并入集合
    for(i=1;i<n;i++){          //要得到源点到各个点的最短路径就需要n-1次循环
        min=MAXINT;
        for(j=1;j<=n;j++)     //找出距离的最小值
            if(!used[i]&&min>dis[j]){
                min=dis[j];
                index=j;
            }
        used[index]=true;   //将该点并入集合
        for(j=1;j<=n;j++)      //更新dis数组
            if(dis[j]>dis[index]+map[index] [j])
                dis[j]=dis[index]+map[index] [j];
    }
}


2.Floyd算法

解决的问题:用于寻找给定的加权图中顶点间的最短路径。

算法的思想:假设求从顶点vi到vj的最短路径。如果从vi到vj有弧,则从vi到vj存在一条长度为map[i] [j]的路径,该路径不一定是最短路径,尚需进行试探。首先考虑路径(vi,v0,vj)是否存在(即判断(vi,v0),(v0,vj)是否存在)。如果存在,则比较(vi,vj)和(vi,vo,vj)的路径长度取长度较短者,然后再并入v1,v2,……进行试探。之所以可以这样去做,是因为从vi到vj的最短路径所经过的点必定在v1,v2,……这个集合里面。而当初我的最主要的疑惑在于为什么k可以0到n-1依次试探,vi到vj的最短路径中可能存在一条v(k+1)到vk的边,而vi和vk之间或vk到vj之间又没有路径可达,那么在判断vk的时候就不会将vk并入路径点的集合中,这样不就出错了吗?实际上是不会的,结合下面的图来看,上面提到的问题实际上就是指在处理vk之前vi到vk的路径是否算出来了。从图中可以看出其实只要vk是路径中的一个点,那么vi和vk之间或vk到vj之间是一定存在路径的,且由于这两条路径所经过的点必定少于从vi到vj的,所以这两条路径必定在之前就已经被算出来了。

最短路径问题 - chhaj5236 - chhaj5236的博客

代码如下:

for(k=0;k<n;k++)
    for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            if(d[i] [k]!=MAXINT&&d[k] [j]!=MAXINT&&d[i] [j]>d[i] [k]+d[k] [j])
                d[i] [j]=d[i] [k]+d[k] [j];
        }


3.Bellman-Ford算法

解决的问题:求解单源最短路径问题,允许存在负权边。

算法的思想:算法运用松弛原理,对每一个顶点v,逐步减小源s到v的最短路径的权的估计值d[v]直到达到实际最短路径的权。假设v是从s可达的任意一个顶点,而p={s,v1,v2,...,vk,v}为任意一条从s到v的无环最短路径。显然路径p最多具有verNum-1条边。在松弛的过程中,每一次外循环都会把edgeNum条边进行松弛,所以第i次外循环必定会更新那些从s经过i条边后到达的点的最小权。所以经过k+1次(最大为verNum-1)外循环,就可以更新所有的单源最短路径。如果存在负环路,那么由于经过负环路可以不断的减小总权值,那么在所有的循环后,再进行一次松弛操作依然可以找到符合松弛条件的边。如果找不到就说明一定不存在负环路。

代码如下:

bool Bellman(int s,int verNum,int edgeNum){
    int i,j;
    for(i=1;i<=verNum;i++)d[i]=MAXINT;
    d[s]=0;
    for(i=1;i<verNum;i++)   //进行verNum-1次松弛操作
        for(j=0;j<edgeNum;j++){  //每次对所有边松弛
            if(d[edge[j].s]!=MAXINT&&d[edge[j].e]>d[edge[j].s]+edge[j].w)
                d[edge[j].e]=d[edge[j].s]+edge[j].w;
        }
    for(i=0;i<edgeNum;i++)
        if(d[edge[i].s]!=MAXINT&&d[edge[i].e]>d[edge[i].s]+edge[i].w)  //判断是否存在负环路
            return false;
    return true;
}


补充:

4.SPFA(Shortest Path Faster Algorithm)算法

解决的问题:求解单源最短路径问题,允许存在负权边。

算法思想:SPFA是对Bellman-Ford算法的一种优化,它优化的关键之处在于意识到了只有那些在前一遍因松弛操作而改变了距离估计值的点,才有可能改变与其邻接的点的估计值。而Bellman-Ford算法对每次都对所有的顶点和边进行松弛,使得算法中含有冗余的操作。SPFA为了消除冗余的计算,其维护了一个队列,初始化时将源点加入队列,每次从队列中取出一个元素,并对其相邻的点进行松弛,如果松弛成功即估计距离得到更新,就将这个相邻顶点入队,直到队列为空为止。根据上面Bellman-Ford的算法思想可知,每个顶点最多被松弛顶点数verNum次,那么用SPFA实现时每个顶点也最多会进队verNum次。所以说如果有一个顶点进队n+1次的话,就可以说明存在负回路。

实现代码:根据上面所讲的思想将Bellman-Ford算法转到SPFA应该是比较简单的,在这里就省略了。

  评论这张
 
阅读(1017)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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