C++实现加权负边有向图最短路径算法 (m条边限制)

本程序旨在解决以下问题：给定一个加权负边有向图，找到从给定源点到给定目标点的成本最低的路径，该路径包含m条边且允许重复经过节点。

输入格式

图的节点数量n和边的数量e
e条边的信息，每条边包含3项内容：顶点1的编号，顶点2的编号，权值
源点和目标点的编号
路径的边数限制m

输出格式

源点到目标点的成本最低的路径长度，如果不存在符合要求的路径，则输出2147483647

示例输入

示例输出

解释

从1到4的路径有两条，分别为1->2->4和1->3->4，其中第一条路径边数为2，第二条路径边数为3，所以选择第一条路径，成本为3+1=4。

代码示例

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

// 定义边结构体
struct Edge {
    int from;
    int to;
    int weight;
};

// 定义状态结构体
struct State {
    int node;
    int cost;
    int edges;
};

// 比较器，用于优先队列
struct CompareState {
    bool operator()(const State& s1, const State& s2) {
        return s1.cost > s2.cost;
    }
};

// 使用Dijkstra算法求解最短路径
int findShortestPath(const vector<vector<Edge>>& graph, int source, int destination, int m) {
    // 初始化距离数组
    vector<int> distances(graph.size(), INT_MAX);
    distances[source] = 0;

    // 使用优先队列存储状态
    priority_queue<State, vector<State>, CompareState> q;
    q.push({source, 0, 0});

    // 循环遍历队列
    while (!q.empty()) {
        State current = q.top();
        q.pop();

        // 如果当前节点为目标节点，且边数符合限制，则返回成本
        if (current.node == destination && current.edges == m) {
            return current.cost;
        }

        // 遍历当前节点的所有邻居
        for (const Edge& edge : graph[current.node]) {
            // 计算邻居节点的成本
            int nextCost = current.cost + edge.weight;

            // 如果当前成本小于邻居节点的最小成本，则更新邻居节点的成本
            if (nextCost < distances[edge.to] && current.edges + 1 <= m) {
                distances[edge.to] = nextCost;
                q.push({edge.to, nextCost, current.edges + 1});
            }
        }
    }

    // 如果不存在符合要求的路径，则返回INT_MAX
    return INT_MAX;
}

int main() {
    // 输入图的节点数量n和边的数量e
    int n, e;
    cin >> n >> e;

    // 初始化图
    vector<vector<Edge>> graph(n);

    // 输入边的信息
    for (int i = 0; i < e; i++) {
        int from, to, weight;
        cin >> from >> to >> weight;
        graph[from - 1].push_back({from - 1, to - 1, weight});
    }

    // 输入源点和目标点的编号
    int source, destination;
    cin >> source >> destination;

    // 输入路径的边数限制m
    int m;
    cin >> m;

    // 求解最短路径
    int shortestPath = findShortestPath(graph, source - 1, destination - 1, m);

    // 输出结果
    if (shortestPath == INT_MAX) {
        cout << 2147483647 << endl;
    } else {
        cout << shortestPath << endl;
    }

    return 0;
}

说明

程序使用Dijkstra算法求解最短路径，并使用优先队列存储状态，状态包含节点、成本和边数。在遍历过程中，如果当前节点为目标节点且边数符合限制，则返回成本。如果不存在符合要求的路径，则返回2147483647。

总结

本程序通过C++实现了一个加权负边有向图最短路径算法，并能根据用户输入的边数限制找到最短路径。程序使用Dijkstra算法进行路径搜索，并使用优先队列存储状态，以确保找到最短路径。该程序能够帮助用户解决现实生活中的路径规划问题，例如交通路线规划、物流配送路线规划等等。