如何用Dijkstra算法求解最长路

Dijkstra算法是一种用于求解最短路径的算法，而不是最长路。如果要求解最长路，需要使用其他算法，如Acyclic Longest Path算法或Bellman-Ford算法。这里以Acyclic Longest Path算法为例进行介绍。

Acyclic Longest Path算法是一种用于有向无环图(DAG)中求解最长路的动态规划算法。它的基本思想是对DAG的所有节点进行拓扑排序，并按照拓扑序列的顺序依次计算每个节点的最长路。具体地，假设有一个有向无环图DAG=(V,E)，其中V表示节点集合，E表示边集合。对DAG进行拓扑排序，得到节点的拓扑序列。对于拓扑序列中的每个节点v，计算其前驱节点的最长路，然后将最长路加上v到其前驱节点的边权值，得到v的最长路。重复上述过程直到计算完所有节点的最长路。

下面是一个使用Acyclic Longest Path算法求解DAG中最长路的C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

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

    vector<vector<pair<int, int>>> graph(n); // 邻接表表示图
    vector<int> in_degree(n, 0); // 记录每个节点的入度
    vector<int> dist(n, -INF); // 记录每个节点的最长路

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w}); // 添加边
        in_degree[v]++; // 统计入度
    }

    queue<int> q; // 拓扑排序所需队列

    // 将入度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
            dist[i] = 0; // 初始距离为0
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto p : graph[u]) {
            int v = p.first, w = p.second;
            dist[v] = max(dist[v], dist[u] + w); // 更新最长路
            if (--in_degree[v] == 0) q.push(v); // 将入度为0的节点加入队列
        }
    }

    for (int i = 0; i < n; i++) {
        cout << "Node " << i << " longest path: " << dist[i] << endl;
    }

    return 0;
}