图中的最短路径问题

Dijkstra算法

基本描述

主要用来解决单源最短路径问题，采用贪心策略，无法解决存在负权值的问题。

实现思路

  1. 首先设置一个集合SS，用来存放已经确定最短路径的顶点；初始化图TT；
  2. 将源点uu加入集合SS并初始化数组dis[i]表示源点到点ii的距离；初始化：dis[u]=0 dis[other]=MAX
  3. 然后从图TT中选取一个与uu直接相连权值最小的点vv加入集合SS；
  4. 对与vv相邻的每个点xx进行松弛操作：dis[x]=min(dis[x],dis[x]+G[v][x])
  5. 重复3 4操作直至TT为空；

示例代码

无优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
struct edge
{
    int to;
    int nextEdge;
    int w;
} e[100010];
int cnt = 0;
int head[100010];
void Dijkstra(int n, int o) // o作为源点
{
    bool S[n + 1];
    int dis[n + 1];
    int pre[n + 1]; // 存放路径(最短路径下某个节点的前一个节点)

    for (int i = 0; i <= n; i++)
    {
        dis[i] = MAX;
        S[i] = false;
    }
    dis[o] = 0;

    while (true)
    {
        int min = MAX;
        int v = 0; // 不存在的节点，方便检查是否连通

        for (int j = 1; j <= n; j++)
        {
            if ((!S[j]) && (dis[j] < min))
            {
                min = dis[j];
                v = j;
            }
        }
        if (v == 0)
        {
            break; // 无法抵达剩余节点或无剩余节点
        }

        S[v] = true;

        // 以v作为中间节点更新dis
        for (int j = head[v]; j; j = e[j].nextEdge)
        {
            int wei_v_to_ = e[j].w;
            if (dis[v] + wei_v_to_ < dis[e[j].to])
            {
                dis[e[j].to] = dis[v] + wei_v_to_;
                pre[e[j].to] = v;
            }
        }
    }
    // 假设终点为n
    if (dis[n] == dis[0])
    {
        return; // 无法抵达终点
    }
	//获取路径
    vector<int> path;
    int pass = n;
    while (pass != o)
    {
        path.push_back(pass);
        pass = pre[pass];
    }
    path.push_back(o);
    for (int i = path.size() - 1; i >= 0; i--)
    {
        cout << path[i];
    }
}

优先队列优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void Dijkstra(int n, int o)
{
    int dis[n + 1];
    int pre[n + 1];
    bool vis[n + 1];
    for (int i = 0; i <= n; i++)
    {
        dis[i] = MAX;
        pre[i] = 0;
    }
    dis[o] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    q.emplace(0, o);

    while (!q.empty())
    {
        pair<long long, int> vv = q.top();
        int v = vv.second;
        q.pop();

        if (vis[v])
        {
            continue;
        }
        vis[v] = true;

        for (int i = head[v]; i; i = e[i].nextE)
        {
            int wei_v_to_ = e[i].w;
            if (dis[v] + wei_v_to_ < dis[e[i].to])
            {
                dis[e[i].to] = dis[v] + wei_v_to_;
                if(!vis[e[i].to])
                	q.emplace(dis[e[i].to], e[i].to);
                pre[e[i].to] = v;
            }
        }
    }
}

Bellman-Ford算法

基本描述

主要解决单源最短路径问题，可以解决含负权值的图，可用来判断图中是否存在负权回路。

实现思路

  1. 初始化数组dis[i]用来表示源点到i的最小距离；
  2. 遍历所有边u−>vu->v如果dis[u]+w<dis[v]dis[u]+w<dis[v]则更新dis[v]；
  3. 重复操作2 n次；

第三步操作有时候并不需要nn次就可以得到完整的disdis数组，而且最坏的情况下也只需要n−1n-1次。第nn次涉及到负权回路的判断，如果图中存在负权回路，则第nn次循环中即使disdis数组已经填写完毕也会继续被更新。

最后如果最短路径的边数有限制，我们可以在每次判断是否更新dis数组时只依赖上一轮循环的dis和边权，并且循环次数限制为k次。例如原来更新dis[v]的条件是dis[u]+w<dis[v]dis[u]+w<dis[v]，这时如果dis[u]在本轮循环中已经更新过一次，则相当于dis[v]在本轮循环一次经过了两条边。

示例代码

一般情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
struct edge
{   int from;
    int to;
    int w;
} e[500010];
int cnt = 0;
long long dis[100010];
int BellmanFord(int n, int s)
{
    for (int i = 0; i <= n; i++)
    {
        dis[i] = MAX;
    }
    dis[s] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= cnt; j++)
        {
            int u = e[j].from;
            int v = e[j].to;
            int w = e[j].w;
            if (dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                if (i == n - 1)
                {
                    return -1;
                }
            }
        }
    }
    return 0;
}

限制边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int BellmanFord(int n, int s, int k)
{
    for (int i = 0; i <= n; i++)
    {
        dis[i] = MAX;
    }
    dis[s] = 0;
    for (int i = 0; i < k; i++)
    {
        //将上一次循环中dist数组的结果存入backup数组
        memcpy(backup, dist, sizeof dist);
        for (int j = 1; j <= cnt; j++)
        {
            int u = e[j].from;
            int v = e[j].to;
            int w = e[j].w;
            if (backup[u] + w < dis[v])
            {
                dis[v] = backup[u] + w;
                if (i == n - 1)
                {
                    return -1;
                }
            }
        }
    }
    return 0;
}

队列优化SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int spfa(int n, int s)
{
    for (int i = 0; i <= n; i++)
    {
        dis[i] = MAX;
    }
    dis[s] = 0;
    bool vis[n + 1] = {false};
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = e[i].nextE)
        {
            int v = e[i].to;
            int w = e[i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                num_edge[v] = num_edge[u] + 1; // 记录最短路径经过的边数
                if (num_edge[v] >= n)          // 多于n条边则经过了负环
                {
                    return -1;
                }
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return 1;
}

Topological-sort 算法

基本描述

对于有向无环图，我们可以先进行拓扑排序，然后依序对边进行松弛。

解释

拓扑排序之后，顶点是按照入度递增的顺序排列的，所以对于源点之前的点一定不可达，对于源点之后的点要么是一步抵达要么是依次抵达。所以对于每个顶点只需要遍历一次所连边。

实现思路

  1. 拓扑排序；
  2. 遍历顶点，对每个顶点的所有边进行松弛；

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void ShortedPath(int n, int s)
{
    vector<int> toPu = ToPu(n);

    for (int i = 0; i <= n; i++)
    {
        dis[i] = MAX;
    }
    dis[s] = 0;

    for (int i = 0; i < toPu.size(); i++)
    {
        for (int j = head[toPu[i]]; j; j = e[j].NextE)
        {
            int u = toPu[i];
            int v = e[j].to;
            int w = e[j].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
            }
        }
    }
}

Floyd算法

基本描述

以上三个算法通常用来解决单源最短路径问题，Floyd算法则通常用来求任意两点间最短路径，复杂度较高，但是常数小容易实现。适用于任何存在最短路径的问题。

实现思路

  1. 类似于dpdp我们定义一个二维数组f[u][v]f[u][v]表示u v之间的最短距离；
  2. 从nn个顶点中选取一个顶点作为u v的中间节点，则f[u][v]=min(f[u][k]+f[k][v],f[u][v])f[u][v]=min(f[u][k]+f[k][v],f[u][v])；

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int k = 1; k <= n; k++)//注意下标
{
    for (int i = 1; i <= n; i++)        
    {            
        for (int j = 1; j <= n; j++)           
        {                
            if (graph[i][j] > graph[i][k] + graph[k][j])
            {
                graph[i][j] = graph[i][k] + graph[k][j];
                pre[i][j] = k;//记录路径
            }
        }
    }
}

Johnson算法

基本描述

JohnsonJohnson算法用来求任意两点间最短路径。FloydFloyd的时间复杂度为O(n3)O(n^3)，但如果我们以每个顶点都为源点，跑nn次DijkstraDijkstra算法就可以达到O(nmlogm)O(nmlogm)的复杂度。但是DijkstraDijkstra​算法只针对不含负权值的图，所以我们需要对边进行预处理。预处理原理和证明见

Johnson算法预处理及正确性证明

实现思路

  1. 新建一个虚拟顶点0，从这个点向其他所有点连接一条权值为0的边；
  2. 使用Bellman−FordBellman-Ford算法求出0点到其他所有顶点的最短路径，记为h[i]h[i]；
  3. 更新u−>vu->v的权值ww为w+h[u]−h[v]w+h[u]-h[v]；
  4. 跑nn轮DijkstraDijkstra算法；

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void Johnson(int n)
{
    // 新建虚拟顶点n+1(也可以是0)
    for (int i = 1; i <= n; i++) // 添加边
    {
        e[++cnt].to = i;
        e[cnt].w = 0;
        e[cnt].nextE = head[n + 1];
        head[n + 1] = cnt;
    }

    spfa(n, n + 1); // 队列优化的Bellman-Ford

    for (int i = 1; i <= n; i++) // 重设权值
    {
        int u = i;
        for (int j = head[u]; j; j = e[j].nextE)
        {
            int v = e[j].to;
            int w = e[j].w;
            e[j].w = w + dis[u] - dis[v];
        }
    }

    vector<int> ans[n];
    for (int i = 1; i <= n; i++)
    {
        vector<int> Dijkstra_dis = Dijkstra(n, i);
        for (int j = 1; j <= n; j++)
        {
            if (Dijkstra_dis[j] == MAX)
            {
                continue;
            }
            ans[i][j] = Dijkstra_dis[j] + dis[j] - dis[i]; // 恢复权值
        }
    }
}