【概述】

所謂 k 短路問題，是指給定一個具有 n 個點 m 條邊的帶正權有向圖，再給定起點 S 與終點 T，詢問從 S 到 T 的所有權和中，第 k 短的路徑的長度。

k 短路問題的解決方法有兩種，一種是利用A*算法求解，另一種是利用最短路算法與可持久化堆結合求解。

【A*算法】

對于 Dijkstra 算法，有一個結論是：當一個點第 k 次出隊的時候，此時路徑長度就是 s 到它的第 k 短路

但直接來寫會造成 MLE，因此要利用 A* 算法來優化狀態數。

首先建立反圖，跑一次最短路算法，得到每個點到 t?的最短路的距離，然后用當前走的距離加上終點的最短路長度作為優化級來進行 A*

因此，當一個點第 k 次出隊時，答案為這個點的優先級，當終點第 k 次出隊時，答案為這個點已走的路徑

struct Edge {int to, next;int w;Edge() {}Edge(int to, int next, int w) : to(to), next(next), w(w) {} }; struct Map {int tot;int head[N];Edge edge[N * N];Map() {tot = 0;memset(head, -1, sizeof(head));}void addEdge(int x, int y, int w) {edge[++tot].to = y;edge[tot].next = head[x];edge[tot].w = w;head[x] = tot;}Edge &operator[](int pos) { return edge[pos]; } }; int n, m; Map G, GT; int dis[N]; bool vis[N]; struct Status{int node;//點編號int diss;//距離int priority;//優先級Status() : node(0), diss(0), priority(dis[0]) {}Status(int node, int diss) : node(node), diss(diss), priority(diss + dis[node]) {}bool operator<(Status b) const { return priority > b.priority; } } status; bool SPFA(int S, int T, int k) { //對反圖求最短路memset(dis, INF, sizeof(dis));memset(vis, false, sizeof(vis));dis[S] = 0;queue<int> Q;Q.push(S);while (!Q.empty()) {int x = Q.front();Q.pop();vis[x] = false;for (int i = GT.head[x]; i != -1; i = GT[i].next) {int y = GT[i].to;if (dis[x] + GT[i].w < dis[y]) {dis[y] = dis[x] + GT[i].w;if (!vis[y]) {Q.push(y);vis[y] = true;}}}}return dis[T] != INF; } int label[N]; int AStar(int S, int T, int k) {memset(label, 0, sizeof(label));if (S == T)k++;priority_queue<Status> Q;Q.push(Status(S, 0));while (!Q.empty()) {Status temp = Q.top();Q.pop();label[temp.node]++;if (temp.node == T && label[temp.node] == k)return temp.diss;for (int i = G.head[temp.node]; i != -1; i = G[i].next)if (label[G[i].to] < k)Q.push(Status(G[i].to, temp.diss + G[i].w));}return -1; } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y, w;scanf("%d%d%d", &x, &y, &w);G.addEdge(x, y, w);GT.addEdge(y, x, w);}int s, t, k;scanf("%d%d%d", &s, &t, &k);if (!SPFA(t, s, k))printf("-1\n");elseprintf("%d\n", AStar(s, t, k));return 0; }

【可持久化堆】

考慮建立反圖，然后跑最短路算法得到以 T 為根的最短路徑生成樹，當走一條非樹邊 (u,v) 時，最終的路徑長度就會因此增加 dis[v]-dis[u]+w

對于一條路徑，我們依次將它經過的非樹邊記下來，約定得到的序列是這條路徑的非樹邊序列。

考慮對于一個合法的非樹邊序列，我們可以找到唯一的一條 S 到 T 的路徑與之對應，因此，k 短路的長度就等于第 k 小的代價和加上 S 到 T 的最短路長度。

考慮如何來得到一個合法的非樹邊序列：

找到一條起點在當前點 p 到根 t 的路徑上的非樹邊

令 p 等于這條邊的終點

我們可以通過這樣的方法來得到所有的非樹邊序列，但是我們并不需要所有的非樹邊序列，因此當找到第 x 短路后再拓展狀態，然后用優先隊列來維護，但這樣每次拓展時間復雜度可達 O(m)，總時間復雜度可以達到 O(mklog?(mk))。

這樣時間復雜度太高，令人無法接受，因為其中被用到的狀態十分少，由于當一個非樹邊序列出隊時，代價和比它大的才可能有用，因此，考慮一個非樹邊序列出隊時通過下面的方法來進行得到新的序列：

追加操作：假如最后一條非樹邊的終點為 v，找到一條起點在 v 到?t 的路徑上代價最小的非樹邊追加在當前非樹邊序列后

替換操作：將最后一條非樹邊更換為代價比它大的 1 條非樹邊

如下圖，橙色虛線是被替換掉的非樹邊，紫色是新加入的非樹邊

考慮用一些可持久化數據結構來維護起點在點 u 到根的路徑上的非樹邊的代價，對于替換操作，當使用可持久化堆時，把最后一條非樹邊替換為它所在的堆中它的左右子節點代表的邊

struct Node{int val,to;Node *left,*right;Node(){}Node(int val, int to, Node *left, Node *right) : val(val), to(to), left(left), right(right) {} }; #define Limit 1000000 Node pool[Limit]; Node *top = pool; Node *newNode(int val, int to) {if (top >= pool + Limit)return new Node(val, to, NULL, NULL);top->val = val;top->to = to;top->left = NULL;top->right = NULL;return top++; } Node *meGTe(Node *a, Node *b) {if (!a)return b;if (!b)return a;if (a->val > b->val)swap(a, b);Node *p = newNode(a->val, a->to);p->left = a->left;p->right = a->right;p->right = meGTe(p->right, b);swap(p->left, p->right);return p; } struct Status {int dist;Node *p;Status(){}Status(int dist, Node *p) : dist(dist), p(p) {}bool operator<(Status b) const { return dist > b.dist; } }; struct Edge {int to, next;int w;Edge() {}Edge(int to, int next, int w) : to(to), next(next), w(w) {} }; struct Map {int tot;int *head;Edge *edge;Map() {}Map(int n, int m) : tot(0) {head = new int[(n + 1)];edge = new Edge[(m + 5)];memset(head, 0, sizeof(int) * (n + 1));}void addEdge(int x, int y, int w) {edge[++tot].to = y;edge[tot].next = head[x];edge[tot].w = w;head[x] = tot;}Edge &operator[](int pos) { return edge[pos]; } }; int n, m; int s, t, k; Map G, GT; bool *vis; int *dis, *pre; queue<int> SPFA(int S) {vis = new bool[(n + 1)];dis = new int[(n + 1)];pre = new int[(n + 1)];memset(dis, INF, sizeof(int) * (n + 1));memset(vis, false, sizeof(bool) * (n + 1));queue<int> Q;Q.push(S);dis[S] = 0;pre[S] = 0;while (!Q.empty()) {int x = Q.front();Q.pop();vis[x] = false;for (int i = GT.head[x]; i; i = GT[i].next) {int y = GT[i].to;int w = GT[i].w;if (dis[x] + w < dis[y]) {dis[y] = dis[x] + w;pre[y] = i;if (!vis[y]) {vis[y] = true;Q.push(y);}}}}return Q; } Node **Hash; void rebuild(queue<int> Q) { //建堆for (int i = 1; i <= n; i++) {for (int j = G.head[i]; j; j = G[j].next) {int to = G[j].to;if (pre[i] != j)G[j].w += dis[to] - dis[i];}}Hash = new Node *[(n + 1)];Q.push(t);Hash[t] = NULL;while (!Q.empty()) {int x = Q.front();Q.pop();if (pre[x])Hash[x] = Hash[G[pre[x]].to];for (int i = G.head[x]; i; i = G[i].next)if (pre[x] != i && dis[G[i].to] != INF)Hash[x] = meGTe(Hash[x], new Node(G[i].w, G[i].to, NULL, NULL));for (int i = GT.head[x]; i; i = GT[i].next) {int y = GT[i].to;if (pre[y] == i)Q.push(y);}} } int kthPath(int k) {if (s == t)k++;if (dis[s] == INF)return -1;if (k == 1)return dis[s];priority_queue<Status> Q;if (!Hash[s])return -1;Q.push(Status(Hash[s]->val, Hash[s]));while (--k && !Q.empty()) {Status x = Q.top();Q.pop();if (k == 1)return x.dist + dis[s];int y = x.p->to;if (Hash[y])Q.push(Status(x.dist + Hash[y]->val, Hash[y]));if (x.p->left)Q.push(Status(x.dist - x.p->val + x.p->left->val, x.p->left));if (x.p->right)Q.push(Status(x.dist - x.p->val + x.p->right->val, x.p->right));}return -1; } int main() {scanf("%d%d", &n, &m);G = Map(n, m);GT = Map(n, m);for (int i = 1, u, v, w; i <= m; i++) {scanf("%d%d%d", &u, &v, &w);G.addEdge(u, v, w);GT.addEdge(v, u, w);}scanf("%d%d%d", &s, &t, &k);queue<int> Q = SPFA(t);rebuild(Q);printf("%d\n", kthPath(k));return 0; }

【例題】

• Remmarguts' Date（POJ-2449）(SPFA+A*)：點擊這里
• Remmarguts' Date（POJ-2449）(SPFA+可持久化堆)：點擊這里

總結

以上是生活随笔為你收集整理的图论 —— k 短路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。