有一无负权有向图。求指定两点间的第二短路径。c++代码

在无负权有向图中寻找两点间的第二短路径可以通过多种算法实现，例如基于Dijkstra算法的变体或者使用Bellman-Ford算法。以下是一个使用Dijkstra算法变体的C++代码示例，该算法可以帮助我们找到最短路径以及次短路径。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 1000; // 假设顶点数量最多为1000
const int INF = INT_MAX;

int n; // 顶点数量
vector<pair<int, int>> adj[MAXN]; // 邻接表表示图，pair中first为邻接点，second为边权

vector<int> dijkstraSecondShortest(int src, int dest) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆
    vector<int> dist(n, INF); // 距离数组
    vector<int> secondDist(n, INF); // 第二短距离数组
    vector<int> prev[MAXN]; // 前驱节点数组

    pq.push({0, src});
    dist[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) continue; // 如果当前节点的最短路径已更新，跳过

        for (auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 如果找到更短的路径
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v].clear();
                pq.push({dist[v], v});
            } else if (dist[u] + weight > dist[v] && dist[u] + weight < secondDist[v]) {
                // 如果找到第二短的路径
                secondDist[v] = dist[u] + weight;
            }

            // 如果当前路径不是最短，但可以作为次短路径的一部分，更新前驱节点
            if (dist[u] + weight == dist[v] && weight < secondDist[u]) {
                prev[v].push_back(u);
            }
        }
    }

    // 回溯找到次短路径
    vector<int> path;
    if (secondDist[dest] != INF) {
        int u = dest;
        while (!prev[u].empty()) {
            for (int p : prev[u]) {
                if (secondDist[u] - dist[u] == dist[p]) {
                    path.push_back(p);
                    u = p;
                    break;
                }
            }
        }
        path.push_back(src);
    }
    return path;
}

int main() {
    // 读入顶点数、边数、源点和目标点
    cin >> n;
    int m, src, dest;
    cin >> m >> src >> dest;

    // 读入边信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 读入边的起点、终点和权重
        adj[u].push_back({v, w});
    }

    // 计算第二短路径
    vector<int> secondShortestPath = dijkstraSecondShortest(src, dest);

    // 输出第二短路径
    for (int i = secondShortestPath.size() - 1; i >= 0; --i) {
        cout << secondShortestPath[i] << " ";
    }
    cout << endl;

    return 0;
}

请注意，上述代码是一个简化的示例，并且假设了图中没有负权边。在实际情况中，你可能需要调整代码以确保它适应具体的问题和限制条件。此外，该代码在查找次短路径时，并没有记录完整的路径信息，只是找出了最短和次短的边。如果需要完整的第二短路径，则需要修改代码以记录路径信息。