算法学习笔记之图论：最短路问题

mastertravels77 · 发表于 2022-1-24 09:16

多源最短路

Dijkstra

在Dijkstra算法中，我们将节点分为「已经求得最短路的点」和「还未求得最短路的点」两个集合。算法须求得所有点的最短路，故需循环n次。在每次循环中从「还未求得最短路的点」中，找出其中距离源点最近的一个点，用这个点更新源点到其它所有点的距离。算法复杂读为O(n^2);
核心代码如下
int dijkstra(){
dist[1] = 0;

for(int i = 0;i < n;i++){
      auto t = -1;
      for(int j = 1;j <= n;j++){
         if(!st[j] && (t == -1 || dist[t] > dist[j]))
            t = j;
      }

      st[t] = true;

      for(int j = 1;j <= n;j++){
         dist[j] = min(dist[j],dist[t] + g[t][j]);
      }
}

if(dist[n] == INF)return INF;
else return dist[n];
}

注：
在最后用t更新其它节点时，那些比t先求得最短路的点其实不会被更新。
Dijkstra算法无法处理含有副权边的情况，原因见下。

考虑反例:
1       1    1
1───────2───────3────── 5
│                ▲
│                │
│                │
└───────────4─────┘
   3          -2根据Dijkstra算法，求得的路径为1->3->5,路径长度为3，但如果走1->4->3->5，长度为2,所以在存在副权边时，Dijkstra算法无法求得正确解。
主要是因为Dijkstra算法每次从「还未求得最短路的点」(即st为false)的点中选取距离源点最近的点(即dist最小)。
初始化阶段所有点的dist最初始化为正无穷,dist[1]被初始化为0;
在第一次循环中，会取t==1,更新过后，dist[1]=0,dist[2]=1,dist[4]=3
在第二次循环中，会取t==2,更新过后，dist[1]=0,dist[2]=1,dist[3]=2,dist[4]=3
在第三次循环中，会取t==3,更新过后，dist[1]=0,dist[2]=1,dist[3]=2,dist[4]=3,dist[5]=3
在第四次循环中，会取t==4,更新过后，dist[1]=0,dist[2]=1,dist[3]=1,dist[4]=3,dist[5]=3
在第五次循环中，会取t==5,更新过后，dist[1]=0,dist[2]=1,dist[3]=2,dist[4]=3,dist[5]=3
堆优化版Dijkstra

void dijkstra(){
priority_queue<PII,vector<PII>,greater<PII>> que;
que.push({0,1});
dist[1] = 0;

while(!que.empty()){
      auto curr = que.top();
      que.pop();

      auto t = curr.second;
      auto dis = curr.first;

      if(st[t])continue;
      else st[t] = true;

      for(int i = h[t];i != -1;i = ne){
         auto j = e;
         if(dist[j] > dist[t] + w){
            dist[j] = dist[t] + w;
            que.push({dist[j],j});
         }
      }
}
if(dist[n] == 0x3f3f3f3f)cout << -1;
else cout << dist[n];
}
插入数据修改小根堆的时间复杂度为 O(logn)，总的复杂度为O(mnlogn),稀疏图m可以看作n，最后的时间复杂度为O(nlog)。当图是绸密图时,m比大n x阶，复杂度为(m^x nlogn),显然不如前者。
Bellmen_ford算法

bellman-ford算法对所有边进行(n-1)松弛操作，只要算法中没有负权回路，bellman-ford算法就能求出最短路。复杂度为O(nm)
该算法与dijkstra算法的思路非常相象，不同之处在于一个对点操作，一个对边操作。
void bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;

for(int i = 0;i < n - 1;i++){
      memcpy(last,dist,sizeof dist);
      for(int j = 0;j < m;j++){
         auto e = edges[j];
         dist[e.b] = min(dist[e.b],last[e.a] + e.c);
      }
}
}
SPFA

仔细看一看bellman-ford算法我们就会发现，在循环当中，有很多边根本不会被更新，只有与一条边相邻的边被更新之后，这条边才会被更新，这提醒我们可以使用queue对算法进行优化。
int spfa(){
queue<int> que;
que.push(1);
dist[1] = 0;
st[1] = true;

while(!que.empty()){
      auto curr = que.front();
      que.pop();
      st[curr] = false;

      for(int i = h[curr];i != -1;i = ne){
         auto j = e;
         if(dist[j] > dist[curr] + w){
            dist[j] = dist[curr] + w;
            if(!st[j]){
                  que.push(j);
                  st[j] = true;
            }
         }
      }
}

return dist[n];
}
一般情况下复杂度为O(m),不过可以构造出一些特殊的数据，使得最坏复杂度为O(nm)
多源最短路

Floyd算法

每次选一个点k做中间结点，对于两点，尝试i-k-j时候比i-j要小。
void floyd(){
for(int k = 1;k <= n;k++){
      for(int i = 1;i <= n;i++){
         for(int j = 1;j <= n;j++){
            d[j] = min(d[j],d[k]+d[k][j]);
         }
      }
}
}
Reference:

		自动登录	找回密码
密码			立即注册