yen算法求k短路c++

下面是使用 Yen算法求K短路的C++代码。其中，我们使用了Dijkstra算法作为最短路径算法的实现。

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 100005;
const int MAXM = 500005;

struct Edge {
    int to, next, w;
} edge[MAXM];

int head[MAXN], edgeNum;
int dis[MAXN], vis[MAXN], pre[MAXN];
int n, m, k;

void addEdge(int u, int v, int w) {
    edge[edgeNum].to = v;
    edge[edgeNum].w = w;
    edge[edgeNum].next = head[u];
    head[u] = edgeNum++;
}

void dijkstra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    dis[s] = 0;
    pq.push(make_pair(dis[s], s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].w) {
                dis[v] = dis[u] + edge[i].w;
                pre[v] = u;
                pq.push(make_pair(dis[v], v));
            }
        }
    }
}

vector<int> Astar(int s, int t, int k) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    vector<int> res;
    if (s == t)
        return res;
    pq.push(make_pair(0, s));
    int cnt = 0;
    while (!pq.empty()) {
        cnt++;
        if (cnt > 1000000)
            break;
        int g = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (u == t) {
            res.push_back(g);
            if (res.size() == k)
                return res;
        }
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (v == pre[u])
                continue;
            pq.push(make_pair(g + edge[i].w + dis[v] - dis[u], v));
        }
    }
    return res;
}

void Yen(int s, int t, int K) {
    vector<vector<int> > paths(K, vector<int>());
    vector<int> candidates;
    dijkstra(s);
    if (dis[t] == INF)
        return;
    candidates = Astar(s, t, 1);
    for (int k = 0; k < K && !candidates.empty(); k++) {
        int w = candidates.back();
        candidates.pop_back();
        paths[k].push_back(s);
        for (int i = t; i != -1; i = pre[i])
            paths[k].push_back(i);
        reverse(paths[k].begin(), paths[k].end());
        for (int i = 0; i < paths[k].size() - 1; i++) {
            int u = paths[k][i];
            int v = paths[k][i + 1];
            for (int j = head[u]; j != -1; j = edge[j].next) {
                if (edge[j].to == v && edge[j].w == w) {
                    edge[j].w = INF;
                    break;
                }
            }
        }
        dijkstra(s);
        candidates = Astar(s, t, 1);
    }
    for (int i = 0; i < K; i++) {
        if (paths[i].empty())
            break;
        cout << "Path " << i + 1 << ": ";
        for (int j = 0; j < paths[i].size(); j++)
            cout << paths[i][j] << " ";
        cout << endl;
    }
}

int main() {
    memset(head, -1, sizeof(head));
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    Yen(1, n, k);
    return 0;
}

其中，dijkstra()函数是使用堆优化的Dijkstra算法实现，Astar()函数是A*算法实现，Yen()函数是Yen算法的具体实现。在Yen()函数中，我们首先使用Dijkstra算法求出起点到终点的最短路径，并使用A*算法求出第一条最短路，然后对于每条路径，我们找出其路径上的边，并将其权值设为无穷大，再次使用Dijkstra算法求出起点到终点的最短路径，并使用A*算法求出新的最短路。重复上述步骤，直到找到K条不同的最短路或者无法找到更多的可行路径为止。