图论(最短路问题)总结

2019/04/14 15:57
阅读数 44

                        图论(最短路)总结  

 关于图论最短路,是联赛常考的考点,需要熟悉掌握,下面总结一下关于最短路的算法。  

  算法一:弗洛伊德(floyd)算法

  这个算法主要是用于求每对顶点(任意两点间的最短路)。是一个非常暴力的算法。

   1.原理:

  根据图的传递闭包思想:

if(d[i][k]+d[j][k])<d[i][j])
    d[i][j]=d[i][k]+d[k][j]

  即每次找一个“中转站K”,如果d[i][k]+d[j][k])<d[i][j],则更新d[i][j].即更新i到j之间的距离。

  2.初始化条件:

  d[i][i]=0;//自己到自己的距离为0;

  d[i][j]=边权;//i与j有直接相连的边。

  d[i][j]=正无穷;//i与j没有直接相连的边。

  3.算法核心:

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

  稳定时间复杂度O(n^3).效率比较低下,一般只在“走投无路”时取得部分分时使用。

  4.探究:

  可定义path[i][j]记录i到j的最短路径中j的前驱顶点,可用于输出最小路径.

  初始化:i到j有边,则path[i][j]=i;path[j][i]=j;

      i到j不连通,则path[i][j]=-1;

  核心:

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

  算法二:迪杰斯特拉(dijkstra)算法

  用于求一个顶点到其他顶点的最短路径(单源最短路径).应用的是贪心的理念,

  目标:图中一个顶点到其他顶点的最短路径,不能有负权。————单源,非负。

  原理:经严格证明的贪心。

  时间复杂度:O(n^2)

  [分析] 开始点(源点):start

  步骤:

  1.用集合1表示已知点,用集合2表示未求点。则1中最初只有start这个点,集合2中有其他n-1个点。

  2.在集合2中找到一个到start距离最近的顶点k,距离=d[k];

  3.把顶点k加到集合1中,同时修改集合2中的剩余顶点j的d[j]是否经过k后变短,如果变短修改d[j];

    if(d[k]+a[k][j]<d[j])  d[j] = d[k]+d[k][j];

  4.重复1,直到集合2为空为止.

  伪代码如下:

 1 for(int i=1;i<=t;i++)
 2         dis[i]=a[st][i];
 3     vis[st]=1;dis[st]=0;
 4     for(int i=1;i<t;i++)
 5     {
 6         int minn=9999999;
 7         int k=0;
 8         for(int j=1;j<=t;j++)
 9             if(!(vis[j])&&(dis[j]<minn))
10             {
11                 minn=dis[j];
12                 k=j;
13             }
14         if(k==0) break ;
15         vis[k]=1;
16         for(int j=1;j<=t;j++)
17             if(!(vis[j])&&(dis[k]+a[k][j]<dis[j]))
18                 dis[j]=dis[k]+a[k][j]; 
19     }

  讨论一:怎样输出路径?

  st:起点;  t:终点;  path[i]:i的前驱顶点;  way:从s到t的结点路径  

  注意:迪杰斯特拉算法不能有负权!

  附:迪杰斯特拉算法还有一个堆优化,但是无法有负权边,联赛常用SPFA算法,性价比高,但是时间复杂度不确定,后文描述.

  算法三:Bellman——ford算法

  我们知道,如果边有负权的话,Dijkstra算法是错误的。

  那么,我们如何判断负环呢?

  Bellman——ford 算法N次迭代就可以判断图中是否有“负环”。

  它取两种边有两种方法:

  ——扫描每一点的邻接表。

  ——用有序点对(x, y)记录边时,可直接取边。但要注意对无向边,要注意(y , x)也要松弛.

    对于求s到某点的最短距离,可能因为其它地方有“负环”而出现问题,要预处理。

  时间复杂度:O(N*E)

  步骤:1.初始化每点到s点的距离为正无穷。

     2.取所有边(x, y),看x能否对y松弛.

     3.如果没有任何松弛,则结束break.

     4.如果松弛次数<N, 转(2);

     5.如果第n次还能松弛,图中有“负环”.

  伪代码略(不常用,一般用队列优化的SPFA)。

  算法四:SPFA(对Bellman——ford算法的优化)

  Bellman——ford算法中,每次都要检查所有的边。这个看起来比较浪费,对于边(x, y),如果上一次dis[x],没有

    改变,则本次的检查显然是多余的。

  我们每次只要从上次刚被松弛过的点x,来看看x能不能松弛其它点即可。

  SPFA算法中用BFS中的队列来存放刚被“松弛”过的点x,来看看x能不能松弛其它点即可。

  时间复杂度:O(K*E)

  算法描述:(伪代码)

 1 void spfa(int k)
 2 {
 3     memset(dis, 0x3f, sizeof(dis));
 4     memset(vis, 0, sizeof(vis));
 5     dis[k] = 0;
 6     vis[k] = 1;
 7     q.push(k);
 8     while(!q.empty())
 9     {
10         int x = q.front();
11         vis[k] = 0;
12         q.pop();
13         for(int i = head[x];i;i = e[i].next)
14         {
15             int tmp = e[i].to;
16             if(dis[x] + e[i].v < dis[tmp])
17             {
18                 dis[tmp] = dis[x] + e[i].v;
19                 if(!vis[tmp])
20                 {
21                     vis[tmp] = 1;
22                     q.push(tmp);
23                 }
24             }
25         }
26     }
27 }

   值得注意的是,该算法在特殊构造的图中很可能退化为O(N*M),需要谨慎使用。

   于是,在这种情况下,出现了一种算法,时间复杂度优秀且稳定。

  这就是堆优化的Dijkstra算法!

  算法五:堆优化的Dijkstra(对Dijkstra算法的优化)

  其实我们发现,在每次贪心修改dis[]数组时,仍做了许多不必要的工作。

  此时我们就可以用堆来维护,优化算法。

  具体见代码:

 1 typedef pair<int, int> pii;
 2 priority_queue <pii, vector<pii>, greater<pii> > q;
 3 int dis[N], vis[N];
 4 void dijkstra(int k){
 5     memset(dis, 0x3f, sizeof(dis));
 6     dis[k] = 0;
 7     q.push(make_pair(dis[k], k));
 8     while(!q.empty()){
 9         pii tmp = q.top();
10         q.pop();
11         int x = tmp.second;
12         if(vis[x]) continue;
13         vis[x] = 1;
14         for(int i = head[x];i;i = e[i].next){
15             int y = e[i].to;
16             if(dis[x] + e[i].v < dis[y]){
17                 dis[y] = dis[x] + e[i].v;
18                 if(!vis[y])
19                     q.push(make_pair(dis[y], y));
20             } 
21         }
22     }
23 }

   值得注意的是,使用dijkstra算法一定要注意图中是否存在负权边!否则后果你懂得。

   总结一下,floyd算法适合暴力拿取部分分,SPFA算法时间复杂度优秀但不稳定,堆优化的dijkstra算法时间复杂度优秀且稳定,但图中不能有负权边。

    具体见题目。  

  

  

 

 

 

 

 

 

 

  

 

 

  

  

 

 

  

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部