最短路算法详解(Dijkstra/SPFA/Floyd)

时间:2023-01-31 04:40:21

转自:http://blog.csdn.net/murmured/article/details/19281031

一、Dijkstra

Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。

 使用邻接矩阵的时间复杂度为O(n^2),用优先队列的复杂度为O((m+n)logn)近似为O(mlogn)

(一)  过程

每次选择一个未访问过的到已经访问过(标记为Known)的所有点的集合的最短边,并用这个点进行更新,过程如下:

Dv为最短路,而Pv为前面的顶点。

最短路算法详解(Dijkstra/SPFA/Floyd)

1.     初始

V

 Known 

 Dv 

Pv

V1

     F

  0

 0

V2

     F

 ∞

0

V3

     F

 ∞

0

V4

      F

 ∞

0

V5  

     F

 ∞

0

V6

    F

 ∞

0

V7

   F

 ∞

0

 

2.     在v1被标记为已知后的表

V

Known

Dv 

 Pv

V1  

  T

0

0

V2

  F

2

V1

V3

  F

0

V4

  F

1

V1

V5

  F

 ∞

0

V6

  F

 ∞

0

V7

  F

0

3.     下一步选取v4并且标记为known,顶点v3,v5,v6,v7是邻接的顶点,而他们实际上都需要调整。如表所示:

V

Known 

Dv 

Pv 

V1 

 T

0

0

V2

 F

2

V1

V3

 F

3

V4

V4

 T

1

V1

V5

 F

3

V4

V6

 F

9

V4

V7

 F

5

V4

 

4.     接下来选取v2,v4是邻接点,但已经是known的,不需要调整,v5是邻接的点但不做调整,因为经过v2的值为2+10=12而长为3的路径已经是已知的。

V

Known 

Dv 

Pv 

V1

  T

 0

0

V2

 T 

 2

V1

V3

 F

 3

V4

V4

 T

 1

V1

V5

 F

 3

V4

V6

 F

 9

V4

V7

 F

 5

V4

 

5.     接下来选取v5,值为3,v7 3+6>5不需调整,然后选取v3,对v6的距离下调到3+5=8

V

Known

Dv 

Pv 

V1

 T

0

0

V2

 T

2

V1

V3

 T

3

V4

V4

 T

1

V1

V5

 T

3

V4

V6

 F

8

V3

V7 

 F

5

V4

 

6.     再选下一个顶点是v7,v6变为5+1=6

V

Known

Dv

 Pv 

V1 

 T

0

0

V2

 T 

2

V1

V3

 T

 3

 V4

V4

 T

 1

 V1

V5  

 T

 3

 V4

V6 

 F

 6

V7

V7

 T

 5

V4

 

7.     最后选取v6

V

Known

Dv

Pv

V1 

 T

 0

V2

 T 

 2

V1 

V3

 T

 3

V4

V4

 T

 1

V1

V5

 T

 3

V4

V6

 T

 6

V7

V7

 T

 5

V4

 

(二)  局限性

Dijkstra没办法解决负边权的最短路径,如图

最短路算法详解(Dijkstra/SPFA/Floyd)

运行完该算法后,从顶点1到顶点3的最短路径为1,3,其长度为1,而实际上最短路径为1,2,3,其长度为0.(因为过程中先选择v3v3被标记为已知,今后不再更新)

(三) 算法实现。

1.普通的邻接表 以(HDU 1874 畅通工程续 SPFA || dijkstra)为例

用vis作为上面标记的known,dis记录最短距离(记得初始化为一个很大的数)。

[cpp] view plaincopyprint?最短路算法详解(Dijkstra/SPFA/Floyd)最短路算法详解(Dijkstra/SPFA/Floyd)
  1. void dijkstra(int s)  
  2. {  
  3.     memset(vis,0,sizeof(vis));         
  4.     int cur=s;                     
  5.     dis[cur]=0;  
  6.     vis[cur]=1;  
  7.     for(int i=0;i<n;i++)  
  8.     {  
  9.         for(int j=0;j<n;j++)                       
  10.             if(!vis[j] && dis[cur] + map[cur][j] < dis[j])   //未被标记且比已知的短,可更新  
  11.                 dis[j]=dis[cur] + map[cur][j] ;  
  12.   
  13.         int mini=INF;  
  14.         for(int j=0;j<n;j++)                    
  15.             if(!vis[j] && dis[j] < mini)    //选择下一次到已知顶点最短的点。  
  16.                 mini=dis[cur=j];  
  17.         vis[cur]=true;  
  18.     }     
  19. }  

2.邻接表+优先队列。

要重载个比较函数.

[cpp] view plaincopyprint?最短路算法详解(Dijkstra/SPFA/Floyd)最短路算法详解(Dijkstra/SPFA/Floyd)
  1. struct point  
  2. {  
  3.     int val,id;  
  4.     point(int id,int val):id(id),val(val){}  
  5.     bool operator <(const point &x)const{  
  6.         return val>x.val;  
  7.     }  
  8. };  
  9. void dijkstra(int s)  
  10. {  
  11.     memset(vis,0,sizeof(vis));  
  12.     for(int i=0;i<n;i++)  
  13.         dis[i]=INF;   
  14.   
  15.     priority_queue<point> q;  
  16.     q.push(point(s,0));  
  17.     dis[s]=0;  
  18.     while(!q.empty())  
  19.     {  
  20.         int cur=q.top().id;  
  21.         q.pop();  
  22.         if(vis[cur]) continue;  
  23.         vis[cur]=true;  
  24.         for(int i=head[cur];i!=-1;i=e[i].next)  
  25.         {  
  26.             int id=e[i].to;  
  27.             if(!vis[id] && dis[cur]+e[i].val < dis[id])  
  28.             {  
  29.                 dis[id]=dis[cur]+e[i].val;  
  30.                 q.push(point(id,dis[id]));  
  31.             }  
  32.         }         
  33.     }  
  34. }  



二、SPFA(bellman-ford)

SPFA是bellman-ford的改进算法(队列实现),效率也更高,故直接介绍SPFA。 相比于Dijkstra,SPFA可以计算带负环的回路。 邻接表的复杂度为:O(kE)E为边数,k一般为2或3

(一)原理过程:


bellman-ford算法的基本思想是,对图中除了源顶点s外的任意顶点u,依次构造从s到u的最短路径长度序列dist[u],dis2[u]……dis(n-1)[u],其中n是图G的顶点数,dis1[u]是从s到u的只经过1条边的最短路径长度,dis2[u]是从s到u的最多经过G中2条边的最短路径长度……当图G中没有从源可达的负权图时,从s到u的最短路径上最多有n-1条边。因此,
dist(n-1)[u]就是从s到u的最短路径长度,显然,若从源s到u的边长为e(s,u),则dis1[u]=e(s,u).对于k>1,dis(k)[u]满足如下递归式,dis(k)[u]=min{dis(k-1)[v]+e(v,u)}.bellman-ford最短路径就是按照这个递归式计算最短路的。
SPFA的实现如下:用数组dis记录更新后的状态,cnt记录更新的次数,队列q记录更新过的顶点,算法依次从q中取出待更新的顶点v,按照dis(k)[u]的递归式计算。在计算过程中,一旦发现顶点K有cnt[k]>n,说明有一个从顶点K出发的负权圈,此时没有最短路,应终止算法。否则,队列为空的时候,算法得到G的各顶点的最短路径长度。

(二)实现:

1.邻接矩阵的SPFA以(HDU 1874 畅通工程续 SPFA || dijkstra)为例 [cpp] view plaincopyprint?最短路算法详解(Dijkstra/SPFA/Floyd)最短路算法详解(Dijkstra/SPFA/Floyd)
  1. void SPFA(int s)    
  2. {    
  3.     for(int i=0;i<n;i++)    
  4.         dis[i]=INF;    
  5.     
  6.     bool vis[MAXN]={0};    
  7.         
  8.     vis[s]=true;    
  9.     dis[s]=0;    
  10.         
  11.     queue<int> q;    
  12.     q.push(s);    
  13.     while(!q.empty())    
  14.     {    
  15.         int cur=q.front();    
  16.         q.pop();    
  17.         vis[cur]=false;    
  18.         for(int i=0;i<n;i++)    
  19.         {    
  20.             if(dis[cur] + map[cur][i] < dis[i])    
  21.             {    
  22.                 dis[i]=dis[cur] + map[cur][i];    
  23.                 if(!vis[i])    
  24.                 {    
  25.                     q.push(i);    
  26.                     vis[i]=true;    
  27.                 }    
  28.             }               
  29.         }    
  30.     }    
  31. }    


2.邻接表的SPFA(推荐)以(HDU 1874 畅通工程续 SPFA || dijkstra)为例 [cpp] view plaincopyprint?最短路算法详解(Dijkstra/SPFA/Floyd)最短路算法详解(Dijkstra/SPFA/Floyd)
  1. void spfa(int s)  
  2. {  
  3.     memset(vis,0,sizeof(vis));  
  4.     for(int i=0;i<n;i++)  
  5.         dis[i]=INF;   
  6.   
  7.     queue<int> q;  
  8.     q.push(s);  
  9.     vis[s]=true;  
  10.     dis[s]=0;  
  11.     while(!q.empty())  
  12.     {  
  13.         int cur=q.front();  
  14.         q.pop();  
  15.         vis[cur]=false;  
  16.         for(int i=head[cur];i!=-1;i=e[i].next)  
  17.         {  
  18.             int id=e[i].to;  
  19.             if(dis[id] > dis[cur]+e[i].val)  
  20.             {  
  21.                 dis[id] = dis[cur] + e[i].val;  
  22.                 if(!vis[id])  
  23.                 {  
  24.                     vis[id]=true;  
  25.                     q.push(id);  
  26.                 }  
  27.             }  
  28.         }  
  29.     }  
  30. }  

3.上面的两个都没有对负圈的判断,因为题目的限制就是正的。判断负环代码如下:以(ZOJ 2770 Burn the Linked Camp 差分约束)为例
[cpp] view plaincopyprint?最短路算法详解(Dijkstra/SPFA/Floyd)最短路算法详解(Dijkstra/SPFA/Floyd)
  1. bool spfa()    
  2. {    
  3.     for(int i=0;i<=n;i++)    
  4.         dis[i]=INF;    
  5.     
  6.     bool vis[MAXN]={0};    
  7.     int cnt[MAXN]={0};    
  8.     queue<int> q;    
  9.     dis[0]=0;    
  10.     vis[0]=true;    
  11.     cnt[0]=1;    
  12.     q.push(0);    
  13.     
  14.     while(!q.empty())    
  15.     {    
  16.         int cur=q.front();    
  17.         q.pop();    
  18.         vis[cur]=false;    
  19.     
  20.         for(int i=head[cur];i!=-1;i=e[i].next)    
  21.         {    
  22.             int id=e[i].to;    
  23.             if(dis[cur] + e[i].val > dis[id])    
  24.             {    
  25.                 dis[id]=dis[cur]+e[i].val;    
  26.                 if(!vis[id])    
  27.                 {    
  28.                     cnt[id]++;    
  29.                     if(cnt[cur] > n)    
  30.                         return false;    
  31.                     vis[id]=true;    
  32.                     q.push(id);    
  33.                 }    
  34.             }    
  35.         }    
  36.     }    
  37.     return true;    
  38. }   

(三):优化

SLF(Small Label First)是指在入队时如果当前点的dist值小于队首, 则插入到队首, 否则插入到队尾。 LLL不太常用,我也没研究。

(四)应用:

眼见的同学应该发现了,上面的差分约束四个字,是的SPFA可以很好的实现差分约束系统。 差分约束系统详解http://blog.csdn.net/murmured/article/details/19285713


三、floyd

全称Floyd-Warshall。记得离散数学里面有Warshall算法,用来计算传递闭包。而数据结构每次都简称floyd,当时就觉得两个都差不多,有神马关系,后来google一下发现是同一个算法。。。。改个名字出来走江湖啊!!!!! 这个算法用于求所有点对的最短距离。比调用n次dijkstra的优点在于代码简单。 时间复杂度为O(n^3)

(一)原理过程:

这是一个dp(动态规划的过程)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 即从顶点i到j且经过顶点k的最短路径长度。

(二)实现:

以(HDU 1874 畅通工程续 SPFA || dijkstra)为例
[cpp] view plaincopyprint?最短路算法详解(Dijkstra/SPFA/Floyd)最短路算法详解(Dijkstra/SPFA/Floyd)
  1. void floyd()  
  2. {  
  3.     for(int k=0;k<n;k++)  
  4.         for(int i=0;i<n;i++)  
  5.             for(int j=0;j<n;j++)  
  6.                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);  
  7. }  




四、其他

如走迷宫经常用的BFS,以一个点出发,向外扩散。

如:

UVA 10047 - TheMonocycle BFS

HDU 1728逃离迷宫 BFS

POJ3984迷宫问题 BFS

UVA 11624 - Fire!图BFS



除了上面的

HDU 1874畅通工程续 SPFA || dijkstra||floyd

还有:

UVA11280 - Flying to Fredericton SPFA变形

UVA11090 - Going in Cycle!! SPFA

UVA10917 Walk Through the Forest SPFA

POJ 3259Wormholes邻接表的SPFA判断负权回路

POJ 1932XYZZY (ZOJ 1935)SPFA+floyd

UVA11374 Airport Express SPFA||dijkstra

 

UVA11367 - Full Tank? dijkstra+DP

 POJ 1511Invitation Cards (ZOJ 2008)使用优先队列的dijkstra

POJ 3268Silver Cow Party (Dijkstra~)

POJ 2387Til the Cows Come Home (Dijkstra)

UVA10603 - Fill BFS~