多段图 每个结点之间的最短路径算法实验C++

本实验使用Dijkstra算法求解多段图中每个结点之间的最短路径。

多段图是一种特殊的有向加权图，其中结点被分为多个阶段，每个阶段内的结点之间没有直接的边相连，只有不同阶段之间的结点才有边相连。因此，多段图可以看作是由若干个子图组成的，每个子图都是一个阶段。

Dijkstra算法是一种贪心算法，用于解决单源最短路径问题。算法运行时维护一个集合S，包含已经找到最短路径的结点，以及一个数组d，记录从源结点到每个结点的最短路径长度。每次从集合V-S中选择一个距离源结点最近的结点u加入集合S中，并更新与u相邻的结点的最短路径长度。算法结束后，d数组中记录的即为源结点到每个结点的最短路径长度。

对于多段图，Dijkstra算法需要进行多次求解，每次求解时只考虑当前阶段内的结点和下一个阶段内的结点之间的边。因此，需要对多段图进行拓扑排序，以确定每个阶段内的结点的顺序。

本实验使用邻接矩阵表示多段图，并实现了Dijkstra算法和拓扑排序算法。以下是完整的C语言代码：

相关问题

最短路径算法区分c++

最短路径算法中，Floyd算法使用一个三维数组 ans[k][i][j]，表示可以经过的中间结点序号小于等于k 时，顶点 i 到顶点 j 的最小代价。具体来说，Floyd算法通过比较顶点i到顶点j的直接路径和通过顶点k的路径之和，来更新最小代价。在算法的每一轮迭代中，通过逐渐增加中间结点的数量，来不断优化最短路径。最后一轮迭代完成后，得到的结果即为所有路径的最短值。

用c++代码求出有n(1<=n<=600)个结点有向图中，结点1到结点n的最短路径,输入格式:第一行有 2 个整数n,m,接下来m行每行有三个整数u,v,w,结点u到v有一条权为w的边(w<10^6)。 输出格式:输出结点1到结点n之间的最短路径，如果1到n之间不存在路径，输出-1。

以下是使用 Dijkstra 算法求解该问题的 C++ 代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

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

    // 初始化邻接表
    vector<pair<int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u-1].push_back({v-1, w});
    }

    // Dijkstra 算法
    int dist[n];
    memset(dist, INF, sizeof(dist));
    dist[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({0, 0});
    while (!heap.empty()) {
        int d = heap.top().first;
        int u = heap.top().second;
        heap.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto p : graph[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap.push({dist[v], v});
            }
        }
    }

    // 输出结果
    if (dist[n-1] == INF) {
        cout << -1 << endl;
    } else {
        cout << dist[n-1] << endl;
    }

    return 0;
}

代码解释：

- 首先读入输入的 n 和 m，表示图中有 n 个结点和 m 条边。
- 然后用邻接表存储图的信息。
- 初始化距离数组 dist，其中 dist[i] 表示结点 1 到结点 i+1 的最短路径长度，初始值为 INF。
- 将结点 1 加入堆中（堆中元素为 (dist[u], u)），表示结点 1 到结点 1 的距离为 0。
- 每次从堆中取出距离最短的结点 u，遍历其所有邻居结点 v，如果从结点 1 到结点 v 的距离可以通过从结点 1 到结点 u 的距离加上 u 到 v 的距离来更新，则更新 dist[v] 的值，并将 (dist[v], v) 加入堆中。
- 最后输出 dist[n-1] 的值，即为结点 1 到结点 n 的最短路径长度。

如果图中存在负权边，可以使用 Bellman-Ford 算法来解决，以下是使用 Bellman-Ford 算法解决该问题的代码：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f;

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

    // 初始化邻接表
    vector<pair<int, int>> graph[n];
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u-1].push_back({v-1, w});
    }

    // Bellman-Ford 算法
    int dist[n];
    memset(dist, INF, sizeof(dist));
    dist[0] = 0;
    for (int i = 0; i < n-1; i++) {
        for (int u = 0; u < n; u++) {
            for (auto p : graph[u]) {
                int v = p.first;
                int w = p.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }

    // 判断是否存在负环
    bool has_negative_cycle = false;
    for (int u = 0; u < n; u++) {
        for (auto p : graph[u]) {
            int v = p.first;
            int w = p.second;
            if (dist[u] + w < dist[v]) {
                has_negative_cycle = true;
                break;
            }
        }
        if (has_negative_cycle) {
            break;
        }
    }

    // 输出结果
    if (has_negative_cycle) {
        cout << -1 << endl;
    } else {
        cout << (dist[n-1] == INF ? -1 : dist[n-1]) << endl;
    }

    return 0;
}

代码解释：

- 首先读入输入的 n 和 m，表示图中有 n 个结点和 m 条边。
- 然后用邻接表存储图的信息。
- 初始化距离数组 dist，其中 dist[i] 表示结点 1 到结点 i+1 的最短路径长度，初始值为 INF。
- 进行 n-1 轮松弛操作，每轮遍历所有边，如果从结点 1 到结点 v 的距离可以通过从结点 1 到结点 u 的距离加上 u 到 v 的距离来更新，则更新 dist[v] 的值。
- 最后判断是否存在负环，如果存在，则说明无法求出最短路径；否则输出 dist[n-1] 的值，即为结点 1 到结点 n 的最短路径长度。如果 dist[n-1] 的值为 INF，则说明结点 1 无法到达结点 n，输出 -1。