跳转阅读

915-更改Dijkstra：求起点到终点的path数组
915-拓扑排序的几种实现方式以及变形
AcWing 853.有边数限制的最短路（Bellman-Ford）

问题描述

前面我们引出了可以用 Dijkstra 求解带权图的最短路径，那么现在如何求解带权有向无环图(DAG)的最长路径呢？

先说结论：可以用拓扑排序和Bellman-Ford算法，但是不能用Dijkstra。也不是说完全不能Dijkstra，只是改动的地方比较多，很多同学提出的思路也都很好！

思路1：更改拓扑排序

1.初始化 dist 数组

在拓扑排序代码的基础上新增 dist 数组，用于记录起点到其余点的最长路径，初始化为负无穷。

2.修改BFS函数

在将入度为 0的节点加入队列时，初始化dist数组中对应的值为 0（因为起点到自身的距离为 0）。
在遍历当前点的邻边时，更新dist数组，通过dist[j] = max(dist[j], dist[t] + w)来计算起点到j点的最长距离，其中w是边的权值。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;

int n, m;
int d[N]; // 入度数组，记录每个节点的入度
int q[N], hh = 0, tt = -1; // 队列，hh表示队头，tt表示队尾
int dist[N]; // 记录起点到其余点的最长路径

struct Node
{
    int id, w;
    Node *next;
    Node(int x, int y) : id(x), w(y), next(NULL) {}
} *head[N]; // 邻接表存储图的边信息

void add(int a, int b, int w)
{
    Node *p = new Node(b, w);
    p->next = head[a];
    head[a] = p;
}

bool bfs()
{
    // 将入度为0的节点加入队列
    for (int i = 1; i <= n; i++)
    {
        if (!d[i])
        {
            q[++tt] = i;
            dist[i] = 0; // 起点到自身的距离为0
        }
    }

    while (hh <= tt)
    {
        int t = q[hh++];

        for (Node *p = head[t]; p; p = p->next)
        {
            int j = p->id, w = p->w;
            // 更新起点到j的最长距离
            dist[j] = max(dist[j], dist[t] + w);
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }

    // 如果队列中的节点个数等于图的节点个数，说明拓扑排序成功
    return tt == n - 1;
}

int main()
{
    cin >> n >> m;
    memset(dist, -0x3f, sizeof dist); // 初始化最长距离为负无穷
    while (m--)
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
        d[b]++; // 记录每个节点的入度
    }

    if (!bfs())
        puts("-1");
    else
    {
        // 输出起点到每个点的最长路径
        for (int i = 1; i <= n; i++)
            printf("dist[%d] = %d\n", i, dist[i]);
    }

    return 0;
}

输入

6 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 1
3 5 3
4 6 4
5 4 2
5 6 5

输出

dist[1] = 0
dist[2] = 1
dist[3] = 4
dist[4] = 9
dist[5] = 7
dist[6] = 13

思路2：更改Dijkstra

• 首先初始化dist数组为-1，将起点1的距离设为0。
• 然后进行n次循环，每次找到未确定最短距离的节点中距离最大的节点t。
• 将节点t标记为已确定最长距离。
• 遍历节点t的邻接表，更新其邻居节点的距离。这里使用max函数更新距离。

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

using namespace std;

const int N = 110;

int n, m;
int dist[N];
bool st[N];

// 定义节点结构体
struct Node
{
    int id, val;
    Node *next;

    Node(int _id, int _val) : id(_id), val(_val), next(NULL) {}
} *head[N];

// 添加边的函数
void add(int a, int b, int c)
{
    Node *p = new Node(b, c);
    p->next = head[a];
    head[a] = p;
}

// Dijkstra算法实现
void dijkstra()
{
    memset(dist, -1, 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[j] > dist[t]))
                t = j;

        st[t] = true;

        for (Node *p = head[t]; p; p = p->next)
        {
            int j = p->id, d = p->val;
            dist[j] = max(dist[j], dist[t] + d);
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    for (int i = 1; i <= n; i++)
        printf("dist[%d] = %d\n", i, dist[i]);

    return 0;
}

输入

4 4
1 2 1
2 3 9
1 3 4
3 4 7

输出

dist[1] = 0
dist[2] = 1
dist[3] = 10
dist[4] = 11

可以发现Dijkstra执行的结果是错误的。

【注意】
其实这里Dijkstra是有问题的，假设有边a->c, b->c，要将st[c] = true的前提应该是a->c和a->b全部访问完，即某一点的所有入边全访问完之后这个点的st才能被更新为true，所以dijkstra将不再适用，只有拓扑排序可以满足这一点，具体的反例如下图所示

思路3：更改Bellman-Ford

更改思路与Dijkstra类似，dist数组初始化为-1，松弛操作中的min改为max，迭代n-1次即可找到起点到其余所有点的最长路径。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f; //定义常量

struct Edge{   //结构体定义边
    int a, b, c;
} edges[M];

int n, m;   //n个点,m条边
int dist[N], last[N]; //dist存储单源最短路径长度,last存储上一次迭代的值

void bellman_ford(){ //Bellman-Ford算法主函数

    memset(dist, -1, sizeof dist); // dist初始化为无穷大

    dist[1] = 0; //源点路径长度设置为0

    // 迭代k次之后的dist代表：不超过k条边的从起点开始的最短路的距离
    for (int i = 0; i < n - 1; i ++) { //k次迭代

        memcpy(last, dist, sizeof dist); //last记录本次迭代前的值

        for (int j = 0; j < m; j ++) {//枚举每条边

            Edge e = edges[j]; //取出一条边

            //松弛操作,更新dist值
            // 这一步是修改的重点
            dist[e.b] = max(dist[e.b], last[e.a] + e.c);
        }
    }
}

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

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

    bellman_ford();

    for (int i = 1; i <= n; i++)
        printf("dist[%d] = %d\n", i, dist[i]);

    return 0;
}

输入

4 4
1 2 1
2 3 9
1 3 4
3 4 7

输出

dist[1] = 0
dist[2] = 1
dist[3] = 10
dist[4] = 17

可以发现Bellman-Ford算法的结果是正确的。

最后提醒

其实类似 22 年压轴题，更改的 dijkstra 算法一样，23 年又来了个更改的拓扑排序算法，24 年难度低没压轴题，不过25的话除了考 Bellman-Ford 和关键路径，会不会又再次更改拓扑排序代码求最长路径来考呢？