图论-最短路问题

问题

图论中的最短路问题，求两个点之间最短距离（路径）的问题；

规定使用 n: 表示点的数量；m: 表示边的数量；边数 m 是顶点数 n 的平方级别视为稠密图

• 稠密图使用邻接矩阵存储（使用 g[N][N]）
• 稀疏图使用邻接表存储（使用数组模拟）
• 只考虑有向图，如果是无向图则建立 2 条双向边即可；默认只考虑有向图

为了方便记忆和实现，图(树)的邻接矩阵或邻接表都使用 vector<vector<int>> 存储, 根据节点数量初始化行数。

// 1. 邻接矩阵
vector<vector<int>> g(N, vector<int>(N, 0));

// 2. 邻接表
vector<vector<int>> g(N);

算法总结：

单源最短路

求从一个点到其他所有点的最短距离，顶点为 1,2,3...n，求顶点 1 到其他所有顶点的最短路

边权都是正数

Dijkstra 基于贪心算法

• 朴素的 Dijkstra 算法 $O(n^2)$ 适用于稠密图，边数多的情形 $m=n^2$，此时比堆优化好
• 堆优化版 Dijkstra 算法 $O(mlogn)$ 适用于稀疏图，m 和 n 同阶的情形 $m<n^2$

朴素 Dijkstra $O(n^2)$

稠密图使用邻接矩阵存储

边权是正数时，如果数据出现自环和重边需要预处理：

• 省略自环
• 重边只保存最短的边

距离都是单源点 1 号点到其他点的距离，使用 dist[N]数组保存当前距离；维护一个已经确定最小距离的点的集合 S，使用了 st[N]数组来标记：

算法思路：

1. 初始化距离: dist[1] = 0, dist[i!=0] = +∞
2. for i: 1~n:       // 迭代n次，每次得到一个最短路径的点
  t <-- 不在S中的点，且距离最近的点
     S <-- t（将t加入到S中)
     用点t来更新其他点的距离

朴素版 Dijkstra 算法
Dijkstra 求最短路 I

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N]; // 邻接矩阵
int dist[N]; // 当前顶点 1 到所有点的距离
bool st[N];  // 是否加入集合 S(已知最短距离的点集合)

int dijkstra()
{
 // 初始化当前的距离
 memset(dist, 0x3f, sizeof dist);
 dist[1] = 0;

 for (int i = 0; i < n; i++)
 {
  int 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]);
 }

 //判断 dist[n]
 if (dist[n] == 0x3f3f3f3f)
  return -1;
 return dist[n];
}

int main()
{
 scanf("%d%d", &n, &m);

 memset(g, 0x3f, sizeof g);

 while (m--)
 {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  // 处理多重边
  g[a][b] = min(g[a][b], c);
 }

 int t = dijkstra();
 printf("%d\n", t);
}

堆优化的 Dijkstra O(mlogn)

稀疏图--使用邻接表存储，方便遍历邻接边，h[N],w[N],e[N],ne[N]

采用 stl 的priority_queue<PII, vector<PII>, greater<PII>> queue;

堆优化版本 Dijkstra 算法
Dijkstra 求最短路 II

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

using PII = pair<int, int>;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;

int dist[N];
bool st[N];

// 邻接表添加边 a --> b (w=c)
void add(int a, int b, int c)
{
 e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dijkstra()
{
 // 初始化距离
 memset(dist, 0x3f, sizeof dist);
 dist[1] = 0;

 priority_queue<PII, vector<PII>, greater<PII>> heap;
 heap.push({0, 1});

 while (heap.size())
 {
  auto t = heap.top();
  heap.pop();

  int ver = t.second, distance = t.first;
  if (st[ver])
   continue;
  // 标记更新过
  st[ver] = true;
  // 只遍历所有的邻边
  for (int i = h[ver]; i != -1; i = ne[i])
  {
   int j = e[i];
   if (dist[j] > distance + w[i])
   {
    dist[j] = distance + w[i];
    heap.push({dist[j], j});
   }
  }
 }

 if (dist[n] == 0x3f3f3f3f)
  return -1;
 return dist[n];
}

int main()
{
 scanf("%d%d", &n, &m);

 // 邻接表的表头初始化
 memset(h, -1, sizeof h);

 while (m--)
 {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  // 有重边也不影响，算法会使用最短的来更新
  add(a, b, c);
 }

 int t = dijkstra();
 printf("%d\n", t);
 return 0;
}

• 这里取出队头后可以添加 dist[ver]=distance ，其可以省略的原因是：由于初始化了起点距离为 0，并且扩展时根据是否距离是否更新更新了距离。

存在负权边

Bellman-Ford 算法 O(nm)
SPFA 一般：O(m)，最坏 O(nm); 是 Bellman-Ford 算法的一个优化，效率比 Bellman-Ford 好

但是不是所有的问题都可以用 SPFA 做，例如最短路边数<=k 的最短路，只能使用 Bellman-Ford 算法

Bellman-Ford 算法 $O(nm)$

边的存储方式：只要能够遍历所有的边就可以；算法思路：

struct edge{
 int a,b,w;
}edges[N];

for 1:n :  // n 次循环
 for 所有边 a,b,w    // 遍历所有边 (a -> b,(w))进行更新
        dist[b]=min(dist[b], dist[a]+w(a,b));

思想：因为最短路径最多为 n-1 个边的组合; 松弛 n-1 次，一定可以松弛完最远的点，得到所有的最短距离

注意： 每次迭代，是对上一个 dist 数组（同一个状态)进行迭代的，对相同的距离状态进行更新（需要先备份）

Bellman-Ford 算法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];

struct Edge
{
 int a, b, w;
} edges[M];

int bellman_ford()
{
 memset(dist, 0x3f, sizeof dist);
 dist[1] = 0;

 for (int i = 0; i < k; i++)
 {
  memcpy(backup, dist, sizeof dist);
  for (int j = 0; j < m; j++)
  {
   int a = edges[j].a, b = edges[j].b, w = edges[j].w;
   dist[b] = min(dist[b], dist[a] + w);
  }
 }
 // if (dist[n] >  0x3f3f3f3f / 2)
 //  return -1;
 // return dist[n];
 // -1 也可能是路径长度
 return dist[n];
}

int main()
{
 cin >> n >> m >> k;

 for (int i = 0; i < m; i++)
 {
  int a, b, w;
  cin >> a >> b >> w;
  edges[i] = {a, b, w};
 }

 int res = bellman_ford();
 if (res > 0x3f3f3f3f / 2)
  puts("impossible");
 else
  cout << res << endl;
 return 0;
}

说明

• 迭代 k 次，表示 1 号点不超过 k 条边的最短距离
• 如果经过 n 次迭代，第 n 次最短路径还有更新，说明这个 n 条边的路径上 n+1 个节点，有环，说明有负环，因此，可以判断有负环，但通常使用 spfa 判断

SPFA （没有负环）

使用邻接表存储，复杂度一般是 O(m)，网格图可能卡成 O(nm)

对 Bellman-Ford 算法的改进，每次迭代中对于任意边a --> b(w)，只有顶点a距离变小了，才有可能更新邻点b的距离

使用一个队列，存储所有距离变小的顶点 a，（优化：使用 st 数组存储顶点是否已经在队列中），算法思路：

1. 初始化距离: dist[1] = 0, dist[i!=0] = +∞
2. queue <-- {0,1} //顶点 1 入队{距离，编号}
while queue 非空：
    t <-- queue.front()
    queue.pop()
    更新 t 的所有出边的终点的距离 t --> b  // 更新
    如果 t 不在队列 queue 中，queue <-- t

注意：没有负环，才能直接用

spfa 算法
spfa 求最短路

#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
// 优化: 标记是否在队列中
bool st[N];

void add(int a, int b, int c)
{
 e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa()
{
 memset(dist, 0x3f, sizeof dist);
 dist[1] = 0;

 queue<int> q;
 q.push(1);
 st[1] = true;
 // 只有更新过的点才能更新其他顶点的距离
 while (!q.empty())
 {
  auto t = q.front();
  q.pop();
  st[t] = false;
  for (int i = h[t]; i != -1; i = ne[i])
  {
   int j = e[i];
   if (dist[j] > dist[t] + w[i])
   {
    dist[j] = dist[t] + w[i];
    if (!st[j])
    {
     q.push(j);
     st[j] = true;
    }
   }
  }
 }
 return dist[n];
}

int main()
{
 scanf("%d%d", &n, &m);

 memset(h, -1, sizeof h);
 for (int i = 0; i < m; i++)
 {
  int x, y, z;
  scanf("%d%d%d", &x, &y, &z);
  add(x, y, z);
 }

 int t = spfa();
 if (t > 0x3f3f3f3f / 2)
  puts("impossible");
 else
  printf("%d\n", t);
 return 0;
}

判断负环：判断(任意一条)最短路径的长度是否>=n (注意这里需要将所有点预先加入队列)，因为负环可能在某些顶点不可到达

不需要维护绝对距离，维护一个 cnt 数组，存储更新后路径上边数，如果有一路径的边数>=n，说明路径上出现负环：

bool spfa()
{
 queue<int> q;
 // 判断负环
 for (int i = 1; i <= n; i++) //可能 1 号点到不了，把所有点都加入
 {
  q.push(i);
  st[i] = true;
 }

 //队列中的点，都是距离缩短的，需要更新它的邻点距离
 while (q.size())
 {
  int t = q.front();
  q.pop();
  st[t] = false;

  for (int i = h[t]; i != -1; i = ne[i])
  {
   int j = e[i];
   if (dist[j] > dist[t] + w[i])
   {
    dist[j] = dist[t] + w[i];
    cnt[j] = cnt[t] + 1; // 更新路径长度

    if (cnt[j] >= n) // 说明有负环
     return true;
    if (!st[j])
    {
     q.push(j);
     st[j] = true;
    }
   }
  }
 }
 return false;
}

说明：有负权回路的图，负环不在路径上也可能求到某点的最短路径

多源汇最短路

起点和终点都不确定/都任意，求所有顶点间的最短路

Floyd 算法 O(n^3) 基于动态规划原理

Floyd 算法 $O(n^3)$

使用邻接矩阵存储d[N][N]顶点间的距离，自己到自己的距离为 0；

算法思路：分阶段d[k,i,j]=min(d[k-1,i,j], d[k-1,i,k]+d[k-1,k,j])

需要没有负权环，数据的预处理：自环（正）可以省略，重边取最短的边

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1 e 9;

int n, m, Q;
int d[N][N];

void floyd()
{
 for (int k = 1; k <= n; k++)
  for (int i = 1; i <= n; i++)
   for (int j = 1; j <= n; j++)
    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
 cin >> n >> m >> Q;

 for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++)
   if (i == j)
    d[i][j] = 0;
   else
    d[i][j] = INF;

 while (m--)
 {
  int a, b, w;
  cin >> a >> b >> w;
  d[a][b] = min(d[a][b], w);
 }

    floyd();
 while (Q--)
 {
  int a, b;
  cin >> a >> b;
  if (d[a][b]>INF/2)
      cout << "impossible" << endl;
  else cout <<d[a][b]<<endl;
 }


}

链接

1. 最短路算法模版