Dijkstra 和反向 Dijkstra 到底分別在什么場(chǎng)景下使用圖中的第 K 短路徑要怎么找如果允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)或者要求路徑不能重復(fù)經(jīng)過(guò)節(jié)點(diǎn)處理方式有什么不同當(dāng)路徑還帶有等待時(shí)間約束時(shí)算法又該如何改造本文會(huì)通過(guò)四類題型由淺入深地講解這些問(wèn)題。一、標(biāo)準(zhǔn) Dijkstra 算法的描述和應(yīng)用Dijkstra 算法是用來(lái)求解非負(fù)權(quán)圖上的單源最短路徑問(wèn)題的經(jīng)典方法從一個(gè)源點(diǎn)出發(fā)求它到圖中其余節(jié)點(diǎn)的最短距離。有向圖和無(wú)向圖都可以使用但只要存在負(fù)權(quán)邊Dijkstra 的貪心性質(zhì)就不再成立這時(shí)需要使用到 Bellman-Ford 算法但這已經(jīng)超出本文的討論范圍。在具體實(shí)現(xiàn)上我們維護(hù)一個(gè)dist數(shù)組dist[v]表示當(dāng)前已經(jīng)找到的、從起點(diǎn)到節(jié)點(diǎn)v的最短距離上界。在算法運(yùn)行過(guò)程之中這個(gè)值可能經(jīng)過(guò)多次松弛而逐漸變小。可以把 Dijkstra 類比成將普通 BFS 的先進(jìn)先出隊(duì)列換成按照當(dāng)前路徑長(zhǎng)度排序的優(yōu)先隊(duì)列更準(zhǔn)確地說(shuō)它每次選取暫定距離最小的狀態(tài)(distance, u)再遍歷u的所有鄰邊。如果經(jīng)過(guò)u能讓相鄰節(jié)點(diǎn)v的距離變得更小就更新dist[v]這一過(guò)程稱為松弛。由于所有邊權(quán)都非負(fù)一個(gè)沒(méi)有過(guò)期的狀態(tài)從堆頂彈出時(shí)對(duì)應(yīng)節(jié)點(diǎn)的最短距離就可以確定下來(lái)。先以 UVa 423 - MPI Maelstrom 為例看一下堆優(yōu)化 Dijkstra 的代碼實(shí)現(xiàn)題目給定由 n 個(gè)處理器組成的網(wǎng)絡(luò)拓?fù)溥厵?quán)代表相鄰處理器之間的通信耗時(shí)。一個(gè)處理器收到消息之后可以立即向所有與它直接相連的處理器發(fā)送消息并且多個(gè)處理器可以同時(shí)發(fā)送。因此消息最早到達(dá)處理器i的時(shí)間就是從處理器1到i的最短距離等到所有處理器都收到消息時(shí)花費(fèi)的總時(shí)間就是這些最短距離中的最大值。輸入格式第一行輸入整數(shù) n處理器數(shù)量滿足 1 ≤ n ≤ 100。后續(xù)輸入描述一個(gè) n × n 的鄰接矩陣 A其中 A(i,j) 代表從處理器 i 直接向處理器 j 發(fā)送消息的通信開銷若輸入為字符x則表示二者之間沒(méi)有直接連接。節(jié)點(diǎn)向自身發(fā)送消息不需要網(wǎng)絡(luò)傳輸因此 A(i,i)0。網(wǎng)絡(luò)為無(wú)向圖滿足 A(i,j)A(j,i)。輸入僅給出鄰接矩陣嚴(yán)格下三角部分第 2 行1 個(gè)數(shù)據(jù) A(2,1)第 3 行2 個(gè)數(shù)據(jù) A(3,1), A(3,2)輸出格式從 1 號(hào)處理器向所有其他處理器廣播消息所需的最短時(shí)間。輸入樣例5 50 30 5 100 20 50 10 x x 10輸出樣例35這一道題目可以采用標(biāo)準(zhǔn) Dijkstra 算法解決。我們用鄰接表存圖用一維數(shù)組記錄處理器1到每個(gè)節(jié)點(diǎn)的當(dāng)前最短距離再使用小根優(yōu)先隊(duì)列按照距離從小到大擴(kuò)展?fàn)顟B(tài)。最后取dist[1...n]的最大值就是完成廣播所需的最短時(shí)間。給出如下的完整代碼#include bits/stdc.h using namespace std; using ll long long; const ll INF numeric_limitsll::max() / 4; using pli pairll, int; struct Edge { int to; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorvectorEdge graph(n1); //鄰接表方式存儲(chǔ)圖 for (int i2;in;i) { for (int j1; ji;j) { string value; cinvalue; if (value!x) { ll weight stoll(value); graph[i].push_back({j, weight}); graph[j].push_back({i, weight}); } } } priority_queuepli, vectorpli, greaterpli pq; vectorll dist(n1, INF); dist[1] 0; pq.push({0, 1}); while (!pq.empty()) { auto [distance, u] pq.top(); pq.pop(); if (distance ! dist[u]) continue; for (const auto e : graph[u]) { int v e.to; if (dist[v] distance e.w) { dist[v] distance e.w; pq.push({dist[v], v}); } } } ll ans 0; for (int i1;in;i) ans max(ans, dist[i]); cout ans endl; return 0; }相關(guān)解釋vectorvectorEdge graph(n1);使用鄰接表存圖并采用從 1 開始的節(jié)點(diǎn)編號(hào)。graph[i]存放所有從節(jié)點(diǎn)i出發(fā)的邊無(wú)向邊需要分別加入兩個(gè)方向。有向圖和無(wú)向圖都可以使用鄰接表只是加邊方式不同。vectorll dist(n1, INF);則記錄從起點(diǎn)到各節(jié)點(diǎn)當(dāng)前已知的最短距離。priority_queuepli, vectorpli, greaterpli pq;定義了小根優(yōu)先隊(duì)列。每個(gè)元素的含義是{從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離, 當(dāng)前節(jié)點(diǎn)編號(hào)}隊(duì)列先比較距離距離相同時(shí)再比較節(jié)點(diǎn)編號(hào)。Dijkstra 真正依賴的是距離較小的狀態(tài)先出隊(duì)節(jié)點(diǎn)編號(hào)只負(fù)責(zé)在距離相同時(shí)確定一個(gè)穩(wěn)定的先后順序不會(huì)影響最短距離的正確性。for (const auto e : graph[u])遍歷節(jié)點(diǎn)u的所有鄰邊。若distance e.w dist[v]說(shuō)明經(jīng)過(guò)u到達(dá)v更短此時(shí)更新dist[v]并把新狀態(tài)加入優(yōu)先隊(duì)列。if (distance ! dist[u]) continue;用來(lái)跳過(guò)過(guò)期狀態(tài)。比如隊(duì)列中先后出現(xiàn){10,u}和{7,u}當(dāng){10,u}出隊(duì)時(shí)dist[u]已經(jīng)被更新為 7那么距離 10 的狀態(tài)就沒(méi)有繼續(xù)擴(kuò)展的必要。這里不是說(shuō)節(jié)點(diǎn)u只能處理一次而是只處理與當(dāng)前最優(yōu)記錄一致的狀態(tài)。在絕大多數(shù)稀疏圖中鄰接表加小根優(yōu)先隊(duì)列都是最常用也最穩(wěn)妥的實(shí)現(xiàn)。采用上面這種允許同一節(jié)點(diǎn)多次入堆、出隊(duì)時(shí)跳過(guò)舊狀態(tài)的寫法時(shí)堆中最多可能出現(xiàn) O(E) 個(gè)狀態(tài)因此也可以把復(fù)雜度寫成 O((VE)log E)。對(duì)于普通簡(jiǎn)單圖E ≤ V2所以通常簡(jiǎn)寫為 O((VE)log V)。空間復(fù)雜度為 O(VE)。鄰接表加優(yōu)先隊(duì)列屬于堆優(yōu)化 Dijkstra尤其適合邊數(shù)遠(yuǎn)小于 V2 的稀疏圖。為了對(duì)照另一種寫法接下來(lái)看 POJ 2387 - Til the Cows Come Home。題目給定一個(gè)正權(quán)無(wú)向圖節(jié)點(diǎn)數(shù)量滿足 2 ≤ V ≤ 1000邊數(shù)量滿足 1 ≤ E ≤ 2000要求節(jié)點(diǎn) V 到節(jié)點(diǎn) 1 的最短距離。輸入格式第1行兩個(gè)整數(shù)E和V即先給定邊數(shù)再給定頂點(diǎn)數(shù)目第2到E1行每行描述一條道路包含三個(gè)用空格分隔的整數(shù)。前兩個(gè)整數(shù)表示道路連接的地標(biāo)編號(hào)第三個(gè)整數(shù)表示道路長(zhǎng)度范圍1到100輸出格式一個(gè)整數(shù)表示貝茜從 V 號(hào)地標(biāo)到 1 號(hào)地標(biāo)必須行走的最短距離。輸入樣例5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100輸出樣例90完整代碼如下#includebits/stdc.h using namespace std; using ll long long; const ll INF numeric_limitsll::max() / 4; int main() { ios::sync_with_stdio(false); cin.tie(0); int E, V; cin E V; vectorvectorll graph(V1,vectorll(V1,INF)); for (int i0;iV;i) graph[i][i] 0; for (int i0;iE;i) { int u, v, w; cin u v w; graph[u][v] min(graph[u][v],(ll)w); graph[v][u] min(graph[v][u],(ll)w); } vectorll dist(V1,INF); vectorbool used(V1,false); dist[V]0; for (int iter1;iterV;iter){ int u-1; for (int i1;iV;i){ if (!used[i] (u-1 || dist[i]dist[u])){ ui; } } if (u-1||dist[u]INF) break; used[u]true; for (int v1;vV;v){ if (!used[v]graph[u][v] ! INF) { if (dist[u]graph[u][v] dist[v]) dist[v] dist[u] graph[u][v]; } } } cout dist[1] endl; return 0; }這道題目還需要處理重邊。比如輸入之中可能同時(shí)存在1 2 20 1 2 15采用鄰接矩陣時(shí)同一對(duì)節(jié)點(diǎn)之間只需要保留最短的那條邊graph[u][v] min(graph[u][v], (ll)w); graph[v][u] min(graph[v][u], (ll)w);dist[i]的含義仍然是從起點(diǎn) V 到節(jié)點(diǎn)i當(dāng)前已知的最短距離初始化為INF表示暫時(shí)無(wú)法到達(dá)。每一輪通過(guò)線性掃描找到一個(gè)尚未確定、且dist最小的節(jié)點(diǎn)u再用dist[u] graph[u][v]松弛其他節(jié)點(diǎn)。由于邊權(quán)非負(fù)u被選中之后它的最短距離就可以確定下來(lái)。上述代碼展示的是 Dijkstra 的樸素實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(V^2)空間復(fù)雜度也是 O(V^2)。需要說(shuō)明的是POJ 2387 本身只有至多 2000 條邊實(shí)際上屬于稀疏圖使用鄰接表加優(yōu)先隊(duì)列會(huì)更合適這里只是借它規(guī)模不大的數(shù)據(jù)展示鄰接矩陣版本。當(dāng) E 接近 V^2 時(shí)圖才是真正的稠密圖此時(shí)鄰接矩陣結(jié)合線性掃描往往更直接也可能比頻繁維護(hù)堆更快。選擇實(shí)現(xiàn)方式時(shí)應(yīng)該先看 E 與 V^2 的關(guān)系而不是默認(rèn)某一種寫法永遠(yuǎn)更優(yōu)。二、A* 算法和第 K 短路徑在標(biāo)準(zhǔn) Dijkstra 算法之中dist數(shù)組只為每個(gè)節(jié)點(diǎn)保留一個(gè)最優(yōu)值。但是如果我們需要找的不是最短路徑而是第 K 短路徑這時(shí)候應(yīng)該如何處理呢一個(gè)直接的想法是不再讓每個(gè)節(jié)點(diǎn)只出隊(duì)一次而是統(tǒng)計(jì)它第幾次從優(yōu)先隊(duì)列中取出。對(duì)于正權(quán)圖第 1 次取出節(jié)點(diǎn)u對(duì)應(yīng)到達(dá)u的最短路徑第 2 次對(duì)應(yīng)第二短依次類推。這個(gè)方法能夠求允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)和邊的第 K 短路但如果直接按照已經(jīng)走過(guò)的距離擴(kuò)展優(yōu)先隊(duì)列中會(huì)出現(xiàn)大量最終到不了終點(diǎn)、或者明顯偏離終點(diǎn)的狀態(tài)。A* 的作用就是利用“距離終點(diǎn)還剩多遠(yuǎn)”來(lái)調(diào)整擴(kuò)展順序盡量少搜索無(wú)關(guān)區(qū)域。下面以 POJ 2449 - Remmarguts Date 為例。題目大意是在有向正權(quán)圖中求從起點(diǎn) S 到終點(diǎn) T 的第 K 短路徑長(zhǎng)度。路徑允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)和邊長(zhǎng)度相同但經(jīng)過(guò)方式不同的路徑也分別計(jì)數(shù)如果不存在第 K 短路徑則輸出-1。輸入格式第一行包含兩個(gè)整數(shù)N和M1 ≤ N ≤ 10000 ≤ M ≤ 1000000。站點(diǎn)編號(hào)從1到N。隨后M行每行包含三個(gè)整數(shù)A、B和T1 ≤ A,B ≤ N1 ≤ T ≤ 100表示存在一條從A站點(diǎn)到B站點(diǎn)的單向小路耗時(shí)為T。最后一行包含三個(gè)整數(shù)S、T和K1 ≤ S,T ≤ N1 ≤ K ≤ 1000。輸出格式單獨(dú)一行輸出一個(gè)整數(shù)表示第 K 短路徑的長(zhǎng)度不存在則輸出-1。輸入樣例4 5 1 2 2 1 3 5 2 4 3 3 4 1 2 3 1 1 4 3輸出樣例6這里可以引出 A* 算法。它是一種啟發(fā)式最短路徑搜索算法核心思想是在 Dijkstra 的基礎(chǔ)上再給每一個(gè)狀態(tài)加上“從當(dāng)前節(jié)點(diǎn)到終點(diǎn)還需要多少代價(jià)”的估計(jì)。標(biāo)準(zhǔn) Dijkstra 只按照起點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離排序行為就像以起點(diǎn)為圓心不斷向外擴(kuò)散A* 則同時(shí)考慮已經(jīng)走了多遠(yuǎn)以及距離目標(biāo)還可能有多遠(yuǎn)因此會(huì)優(yōu)先擴(kuò)展更有希望較早到達(dá)終點(diǎn)的狀態(tài)。A* 會(huì)給每個(gè)待搜索狀態(tài)計(jì)算評(píng)價(jià)函數(shù)f(n) g(n) h(n)。其中g(shù)(n)表示從起點(diǎn) S 到節(jié)點(diǎn) n 已經(jīng)付出的實(shí)際代價(jià)h(n)表示從節(jié)點(diǎn) n 到終點(diǎn) T 的估計(jì)代價(jià)搜索時(shí)優(yōu)先取出f(n)更小的狀態(tài)。值得注意的是標(biāo)準(zhǔn) Dijkstra 可以看成h(n)0的特殊情況。為了保證搜索順序的正確性啟發(fā)函數(shù)通常要求不能高估真實(shí)距離并且在滿足此條件下啟發(fā)函數(shù)越接近真實(shí)值A(chǔ)*算法搜索效率和正確率也就越高擴(kuò)展的無(wú)效節(jié)點(diǎn)也就越少。也就是需要滿足以下兩個(gè)條件可容許性對(duì)任意節(jié)點(diǎn)nh(n)不能大于從n到終點(diǎn)的真實(shí)最短距離。即h(n) ≤ d(n,target)其中d(n, target)是節(jié)點(diǎn)n到終點(diǎn)的真實(shí)最短距離。這是為了保證A*找到的是真正的最短路徑。一致性對(duì)于任意邊W(a,b)滿足h(a) \leq w(a,b) h(b)其中w(a,b)是a 到b的權(quán)值。這是可容許行更強(qiáng)的條件。而在這道題中我們直接在反圖上從終點(diǎn)執(zhí)行一次 Dijkstra得到原圖中每個(gè)節(jié)點(diǎn)到終點(diǎn)的真實(shí)最短距離。也就是說(shuō)這里的h(n)不是大概估計(jì)而是一個(gè)精確的啟發(fā)函數(shù)。為什么要建反圖原圖中的邊是u - v反圖中就存成v - u。從終點(diǎn) T 在反圖上運(yùn)行 Dijkstra得到的h[u]恰好就是原圖中從u到 T 的最短距離。若h[u]為無(wú)窮大說(shuō)明從u根本無(wú)法到達(dá)終點(diǎn)這類狀態(tài)可以直接剪掉。#include functional #include iostream #include limits #include queue #include vector using namespace std; using ll long long; using pli pairll, int; const ll INF numeric_limitsll::max() / 4; struct Edge { int to; int weight; }; struct State { int node; ll g; ll f; bool operator(const State other) const { if (f ! other.f) return f other.f; return g other.g; } }; ? int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorEdge graph(n 1); vectorvectorEdge reverseGraph(n 1); for (int i 0; i m; i) { int a, b, cost; cin a b cost; graph[a].push_back({b, cost}); reverseGraph[b].push_back({a, cost}); } int start, target, k; cin start target k; vectorll h(n 1, INF); priority_queuepli, vectorpli, greaterpli dijkstraQueue; ? h[target] 0; dijkstraQueue.push({0, target}); ? while (!dijkstraQueue.empty()) { auto [distance, u] dijkstraQueue.top(); dijkstraQueue.pop(); ? if (distance ! h[u]) continue; ? for (const Edge edge : reverseGraph[u]) { int v edge.to; ll newDistance distance edge.weight; ? if (newDistance h[v]) { h[v] newDistance; dijkstraQueue.push({newDistance, v}); } } } ? if (h[start] INF) { cout -1 \n; return 0; } if (start target) k; ? priority_queueState, vectorState, greaterState open; vectorint popCount(n 1, 0); ? open.push({start, 0, h[start]}); ? while (!open.empty()) { State current open.top(); open.pop(); ? int u current.node; popCount[u]; ? if (u target popCount[u] k) { cout current.g \n; return 0; } ? if (popCount[u] k) continue; ? for (const Edge edge : graph[u]) { int v edge.to; if (h[v] INF || popCount[v] k) continue; ? ll newG current.g edge.weight; open.push({v, newG, newG h[v]}); } } ? cout -1 \n; return 0; }結(jié)構(gòu)體State表示優(yōu)先隊(duì)列中的一個(gè)搜索狀態(tài)把當(dāng)前節(jié)點(diǎn)node、已經(jīng)走過(guò)的實(shí)際距離g、預(yù)計(jì)經(jīng)過(guò)終點(diǎn)時(shí)的總距離fgh放在一起。重載之后小根堆會(huì)優(yōu)先取出f較小的狀態(tài)若f相同再優(yōu)先取出g較小的狀態(tài)。建圖時(shí)同時(shí)保存原圖和反圖。反向 Dijkstra 得到的h[i]表示原圖中從節(jié)點(diǎn)i到終點(diǎn)的真實(shí)最短距離。它不僅給 A* 提供搜索方向也可以提前過(guò)濾h[v] INF的節(jié)點(diǎn)因?yàn)檫@些節(jié)點(diǎn)無(wú)論如何都無(wú)法走到終點(diǎn)。popCount[u]記錄節(jié)點(diǎn)u已經(jīng)有效出隊(duì)多少次。與標(biāo)準(zhǔn) Dijkstra 不同這里不能在第一次取出u后就永遠(yuǎn)丟掉其他到達(dá)方式因?yàn)榈?2 次、第 3 次到達(dá)u的路徑仍然可能組成最終答案。由于邊權(quán)為正優(yōu)先隊(duì)列按照f(shuō)擴(kuò)展而終點(diǎn)處滿足h[target]0所以終點(diǎn)第 K 次出隊(duì)時(shí)對(duì)應(yīng)的g就是第 K 短路徑長(zhǎng)度。open是 A* 的候選狀態(tài)隊(duì)列。每次取出f最小的狀態(tài)遍歷它的出邊再把新的候選放回隊(duì)列。它保存的是一條條路徑狀態(tài)而不是每個(gè)節(jié)點(diǎn)唯一的最短距離所以同一個(gè)節(jié)點(diǎn)可以在隊(duì)列中出現(xiàn)多次真正限制有效擴(kuò)展次數(shù)的是popCount。如果start target初始狀態(tài){start, 0, h[start]}會(huì)先把長(zhǎng)度為 0 的空路徑算作一次到達(dá)。但原題要求的是實(shí)際經(jīng)過(guò)邊的路徑所以代碼中需要先執(zhí)行k把空路徑跳過(guò)去。這里用反向 Dijkstra 求出的h[i]是精確最短距離不是估計(jì)值。它同時(shí)滿足可容許性和一致性因此 A* 不僅能保證找到第 K 短路而且每個(gè)狀態(tài)第一次出隊(duì)時(shí)就是該節(jié)點(diǎn)在當(dāng)前 g 下的最優(yōu)擴(kuò)展順序。如果換成一個(gè)粗糙的估計(jì)函數(shù)雖然也可能正確但搜索效率會(huì)明顯下降。這里求的是允許重復(fù)節(jié)點(diǎn)和邊的第 K 短“游走”只是競(jìng)賽題中通常仍然簡(jiǎn)稱為第 K 短路。不同路徑即使長(zhǎng)度相同也要分別計(jì)數(shù)所以優(yōu)先隊(duì)列中的重復(fù)狀態(tài)不能簡(jiǎn)單去重。反向 Dijkstra 的復(fù)雜度為 O((NM)\log N)A* 階段中每個(gè)節(jié)點(diǎn)最多有效擴(kuò)展 K 次粗略上界可以寫成 O(KM\log(KM))。啟發(fā)函數(shù)主要減少實(shí)際擴(kuò)展的無(wú)關(guān)狀態(tài)但不會(huì)改變這里給出的最壞復(fù)雜度上界。三、Yen 算法思想和第 K 短簡(jiǎn)單路徑上一道題允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)和邊因此同一個(gè)節(jié)點(diǎn)可以被多次擴(kuò)展。但是如果題目要求路徑中不能重復(fù)經(jīng)過(guò)節(jié)點(diǎn)這種“統(tǒng)計(jì)終點(diǎn)第幾次出隊(duì)”的方法就不能直接使用了。下面介紹 UVa 1685 - Enjoyable Commutation這道題要求的正是第 K 短簡(jiǎn)單路徑。題目給定一個(gè)帶正權(quán)的有向圖需要求從起點(diǎn) a 到終點(diǎn) b 的第 K 短路徑滿足一條路徑不能重復(fù)經(jīng)過(guò)同一個(gè)節(jié)點(diǎn)也就是必須是簡(jiǎn)單路徑先按照路徑總長(zhǎng)度從小到大排序如果兩條路徑長(zhǎng)度相同再按照節(jié)點(diǎn)序列的字典序排序如果不足 K 條路徑輸出None否則用連字符輸出第 K 條路徑經(jīng)過(guò)的節(jié)點(diǎn)。每組數(shù)據(jù)的第一行包含n m k a b其中 2 \leq n \leq 501 \leq k \leq 200。接下來(lái)的 m 行每行給出一條有向邊x y d。題目保證不存在自環(huán)同一對(duì)有序節(jié)點(diǎn)之間也不會(huì)出現(xiàn)重邊。輸入以五個(gè) 0 結(jié)束。輸入樣例5 20 10 1 5 1 2 1 1 3 2 1 4 1 1 5 3 2 1 1 2 3 1 2 4 2 2 5 2 3 1 1 3 2 2 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 5 2 5 1 1 5 2 1 5 3 1 5 4 1 4 6 1 1 4 2 4 2 1 3 2 1 2 1 1 4 3 2 3 1 3 4 1 3 3 5 1 3 1 2 1 2 3 1 1 3 1 0 0 0 0 0輸出樣例1-2-4-3-5 1-2-3-4 None這道題可以采用 Yen 算法解決。Yen 算法先求出第一短的簡(jiǎn)單路徑然后依次構(gòu)造第二短、第三短直到得到第 K 短。假設(shè)當(dāng)前已經(jīng)確定的一條路徑為1 - 2 - 4 - 6任何一條與它不同的新路徑都一定存在一個(gè)“第一次發(fā)生偏離的位置”。這個(gè)位置可能在節(jié)點(diǎn) 1、節(jié)點(diǎn) 2也可能在節(jié)點(diǎn) 4。于是我們可以依次把這些節(jié)點(diǎn)當(dāng)作偏離點(diǎn)將整條路徑拆成兩部分完整路徑 rootPath spurPath其中rootPath是從起點(diǎn)到偏離點(diǎn)的公共前綴spurPath是從偏離點(diǎn)重新走向終點(diǎn)的后半段。為了讓新路徑既不同于已有答案又仍然是簡(jiǎn)單路徑需要做兩類限制禁止rootPath中偏離點(diǎn)之前的所有節(jié)點(diǎn)防止后半段繞回前綴并重復(fù)經(jīng)過(guò)節(jié)點(diǎn)對(duì)所有與當(dāng)前rootPath前綴相同的已有答案禁止它們?cè)谄x點(diǎn)之后使用的那條邊防止重新生成已經(jīng)確定的路徑。每個(gè)偏離點(diǎn)都可能產(chǎn)生一條候選路徑這些候選不能在本輪結(jié)束后丟掉因?yàn)榈谝粭l路徑產(chǎn)生的某個(gè)候選也可能直到第五輪才成為最優(yōu)答案。所以代碼使用一個(gè)全局候選集合candidates按照“總長(zhǎng)度、節(jié)點(diǎn)序列字典序”排序。每一輪從中取出最小者作為下一條正式答案。還需要解決一個(gè)子問(wèn)題在刪除部分節(jié)點(diǎn)和邊之后如何找到長(zhǎng)度最短、且字典序最小的路徑這里先在反圖上從終點(diǎn)執(zhí)行 Dijkstra得到dist[u]表示節(jié)點(diǎn)u到終點(diǎn)的最短距離。然后從起點(diǎn)正向恢復(fù)路徑每一步在所有滿足dist[u] w(u,v) dist[v]的鄰邊中選擇終點(diǎn)編號(hào)最小的一個(gè)。距離條件保證最終仍然是最短路徑鄰接點(diǎn)從小到大選擇則保證節(jié)點(diǎn)序列的字典序最小。完整代碼如下#include bits/stdc.h using namespace std; ? using ll long long; const ll INF (1LL 62); ? struct Edge { int to; int w; }; ? struct Path { ll dist; // 路徑總長(zhǎng)度 vectorint nodes; // 路徑上的節(jié)點(diǎn)序列 }; ? struct PathCmp { bool operator()(const Path a, const Path b) const { if (a.dist ! b.dist) return a.dist b.dist; return a.nodes b.nodes; } }; ? int n, m, K, startNode, goalNode; vectorvectorEdge graphAdj, reverseAdj; vectorvectorint weightEdge; ? bool shortestPath( int source, int target, const vectorchar bannedNode, const setpairint, int bannedEdge, Path result ) { if (bannedNode[source] || bannedNode[target]) return false; ? vectorll dist(n 1, INF); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; ? dist[target] 0; pq.push({0, target}); ? while (!pq.empty()) { auto [currentDist, v] pq.top(); pq.pop(); ? if (currentDist ! dist[v]) continue; ? // 反圖中的 v - u 對(duì)應(yīng)原圖中的 u - v。 for (const Edge e : reverseAdj[v]) { int u e.to; ? if (bannedNode[u] || bannedNode[v]) continue; if (bannedEdge.count({u, v})) continue; ? ll newDist currentDist e.w; if (newDist dist[u]) { dist[u] newDist; pq.push({newDist, u}); } } } ? if (dist[source] INF) return false; vectorint nodes; nodes.push_back(source); ? int current source; while (current ! target) { int nextNode -1; ? // graphAdj[current] 已經(jīng)按終點(diǎn)編號(hào)升序排列。 for (const Edge e : graphAdj[current]) { int v e.to; ? if (bannedNode[v]) continue; if (bannedEdge.count({current, v})) continue; if (dist[v] INF) continue; ? if (dist[current] (ll)e.w dist[v]) { nextNode v; break; } } ? if (nextNode -1) return false; ? nodes.push_back(nextNode); current nextNode; } ? result.dist dist[source]; result.nodes move(nodes); return true; } ? int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ? while (cin n m K startNode goalNode) { if (n 0 m 0 K 0 startNode 0 goalNode 0) { break; } ? graphAdj.assign(n 1, {}); reverseAdj.assign(n 1, {}); weightEdge.assign(n 1, vectorint(n 1, -1)); ? for (int i 0; i m; i) { int x, y, d; cin x y d; ? graphAdj[x].push_back({y, d}); reverseAdj[y].push_back({x, d}); weightEdge[x][y] d; } for (int u 1; u n; u) { sort(graphAdj[u].begin(), graphAdj[u].end(), [](const Edge a, const Edge b) { return a.to b.to; }); } ? vectorchar noBannedNode(n 1, false); setpairint, int noBannedEdge; ? Path firstPath; if (!shortestPath(startNode, goalNode, noBannedNode, noBannedEdge, firstPath)) { cout None\n; continue; } ? vectorPath answers; answers.push_back(firstPath); ? // candidates 自動(dòng)按照題目要求排序并且自動(dòng)去重。 setPath, PathCmp candidates; ? // 額外記錄已成為答案的節(jié)點(diǎn)序列防止極端情況下重復(fù)加入。 setvectorint acceptedPaths; acceptedPaths.insert(firstPath.nodes); ? while ((int)answers.size() K) { const Path previousPath answers.back(); int pathSize (int)previousPath.nodes.size(); ? // rootCost 表示從起點(diǎn)到當(dāng)前偏離點(diǎn)的前綴長(zhǎng)度。 ll rootCost 0; ? for (int spurIndex 0; spurIndex 1 pathSize; spurIndex) { int spurNode previousPath.nodes[spurIndex]; ? // 當(dāng)前根路徑為 previousPath[0 ... spurIndex]。 vectorint rootPath( previousPath.nodes.begin(), previousPath.nodes.begin() spurIndex 1 ); ? // 禁止根路徑中除 spurNode 外的節(jié)點(diǎn)保證最終路徑不重復(fù)訪問(wèn)節(jié)點(diǎn)。 vectorchar bannedNode(n 1, false); for (int i 0; i spurIndex; i) { bannedNode[rootPath[i]] true; } setpairint, int bannedEdge; ? for (const Path path : answers) { if ((int)path.nodes.size() spurIndex) continue; ? bool samePrefix true; for (int i 0; i spurIndex; i) { if (path.nodes[i] ! rootPath[i]) { samePrefix false; break; } } ? if (samePrefix spurIndex 1 (int)path.nodes.size()) { bannedEdge.insert({ path.nodes[spurIndex], path.nodes[spurIndex 1] }); } } ? Path spurPath; if (shortestPath(spurNode, goalNode, bannedNode, bannedEdge, spurPath)) { vectorint totalNodes rootPath; ? // spurPath 的第一個(gè)節(jié)點(diǎn)就是 spurNode避免重復(fù)加入。 totalNodes.insert(totalNodes.end(), spurPath.nodes.begin() 1, spurPath.nodes.end()); ? Path totalPath; totalPath.dist rootCost spurPath.dist; totalPath.nodes move(totalNodes); ? if (!acceptedPaths.count(totalPath.nodes)) { candidates.insert(move(totalPath)); } } ? int u previousPath.nodes[spurIndex]; int v previousPath.nodes[spurIndex 1]; rootCost weightEdge[u][v]; } ? if (candidates.empty()) break; ? auto it candidates.begin(); Path nextPath *it; candidates.erase(it); ? acceptedPaths.insert(nextPath.nodes); answers.push_back(move(nextPath)); } ? if ((int)answers.size() K) { cout None\n; } else { const vectorint result answers[K - 1].nodes; for (int i 0; i (int)result.size(); i) { if (i 0) cout -; cout result[i]; } cout \n; } } ? return 0; }代碼中有幾個(gè)地方需要重點(diǎn)理解answers保存已經(jīng)正式確定的路徑candidates保存所有尚未被選中的候選路徑。candidates定義在外層循環(huán)之外因此以前產(chǎn)生但暫時(shí)沒(méi)有入選的路徑會(huì)一直保留這正是 Yen 算法不能缺少的候選池。bannedNode只禁止根路徑中spurNode之前的節(jié)點(diǎn)不禁止偏離點(diǎn)本身。否則無(wú)法從偏離點(diǎn)出發(fā)尋找新的后綴如果完全不禁前綴節(jié)點(diǎn)新后綴又可能繞回前面生成帶重復(fù)節(jié)點(diǎn)的路徑。bannedEdge需要檢查所有已經(jīng)進(jìn)入answers的路徑。只禁止上一條答案使用的邊是不夠的否則可能重新生成更早已經(jīng)出現(xiàn)過(guò)的路徑。shortestPath每次都在當(dāng)前的禁點(diǎn)、禁邊條件下重新求最短路。由于原題邊權(quán)嚴(yán)格為正根據(jù)dist恢復(fù)路徑時(shí)不會(huì)陷入零權(quán)環(huán)同時(shí)題目保證同一對(duì)有序節(jié)點(diǎn)之間至多一條邊所以可以直接使用(u,v)表示一條被禁用的邊并使用weightEdge[u][v]計(jì)算前綴長(zhǎng)度。Yen 算法正確性的關(guān)鍵就在“第一次偏離”上。任意一條尚未進(jìn)入答案集合的簡(jiǎn)單路徑與某一條已有路徑相比都可以找到第一個(gè)不同的邊。枚舉已有路徑上的每個(gè)偏離點(diǎn)就不會(huì)漏掉它可能對(duì)應(yīng)的候選而每次從全局候選池中取出排序最小的路徑又保證了新加入answers的確實(shí)是下一條路徑。一次shortestPath主要執(zhí)行一次堆優(yōu)化 Dijkstra復(fù)雜度約為 O((NM)\log N)。一條簡(jiǎn)單路徑最多包含 N 個(gè)節(jié)點(diǎn)生成一條新答案時(shí)最多調(diào)用 O(N) 次最短路所以核心復(fù)雜度可以粗略寫成 O(KN(NM)\log N)。當(dāng)前代碼為了判斷相同前綴還會(huì)直接掃描已有答案最壞會(huì)額外產(chǎn)生 O(K^2N^2) 的前綴比較候選路徑本身最多占用 O(KN^2) 的空間。在本題 N \leq 50、K \leq 200 的范圍內(nèi)這樣的寫法更直觀也足以應(yīng)對(duì)數(shù)據(jù)范圍。四、另一種 K 短路允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)并帶有等待約束第二部分的 POJ 2449 已經(jīng)允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)和邊這一部分真正增加的難點(diǎn)不是“允許重復(fù)”而是邊的代價(jià)會(huì)隨到達(dá)時(shí)間發(fā)生變化。下面以 UVa 1684 - Escape Plan 為例。題目中有 N 個(gè)星球編號(hào)為 0 到 N-1其中 0 是起點(diǎn)N-1 是終點(diǎn)。星球之間存在單向的超空間隧道每條隧道由四個(gè)整數(shù)U V C W描述隧道從U指向V通過(guò)隧道需要花費(fèi)W秒隧道只會(huì)在時(shí)間 0,C,2C,3C,\dots 開放在任意一個(gè)星球上連續(xù)等待的時(shí)間不能超過(guò)T秒。有 K 艘帝國(guó)殲星艦會(huì)沿著較短的路線追擊因此需要求從 0 到 N-1 的第 K1 短路徑。路徑允許重復(fù)經(jīng)過(guò)節(jié)點(diǎn)和邊花費(fèi)時(shí)間相同的不同走法也要分別計(jì)數(shù)。如果不存在這樣的路徑輸出-1。每組數(shù)據(jù)第一行包含N M K T滿足 1 \leq N \leq 1000 \leq M \leq 5000 \leq K \leq 90 \leq T \leq 100。每條邊的周期滿足 1 \leq C \leq 10通過(guò)隧道的時(shí)間滿足 1 \leq W \leq 10^6。輸入以四個(gè) 0 結(jié)束。輸入樣例5 9 2 2 1 2 5 5 2 4 6 6 0 2 1 8 1 4 4 3 3 0 1 8 1 3 5 10 0 4 4 4 2 3 3 4 3 1 5 10 10 0 0 0 0 0 0 0輸出樣例Case 1: 28 Case 2: -1如果仍然只把“當(dāng)前位于哪個(gè)節(jié)點(diǎn)”作為狀態(tài)就會(huì)丟失必要的信息。比如同樣到達(dá)節(jié)點(diǎn)u到達(dá)時(shí)間分別為 8 和 9面對(duì)一條每 3 秒開放一次的隧道接下來(lái)需要等待的時(shí)間并不相同。因此這里需要把狀態(tài)寫成(node, phase)其中phase是當(dāng)前總時(shí)間對(duì)所有隧道周期最小公倍數(shù)的余數(shù)。因?yàn)?1 \leq C \leq 10所有周期的最小公倍數(shù)最多為lcm(1,2,...,10) 2520只要兩個(gè)到達(dá)時(shí)間模period相同它們面對(duì)每一條隧道時(shí)的開放情況就完全相同。這樣一來(lái)原本隨絕對(duì)時(shí)間變化的問(wèn)題就被展開成了至多 N \times 2520 個(gè)有限狀態(tài)。假設(shè)當(dāng)前時(shí)間對(duì)周期的余數(shù)為phase準(zhǔn)備經(jīng)過(guò)周期為cycle的邊。距離最近一次可出發(fā)時(shí)間還需要等待int firstWait (cycle - phase % cycle) % cycle;但是不能只考慮最近的一次開放。如果firstWait cycle、firstWait 2 * cycle仍然不超過(guò)T主動(dòng)多等一段時(shí)間也是合法選擇并且可能影響后續(xù)邊的開放時(shí)刻。所以代碼需要枚舉firstWait, firstWait cycle, firstWait 2 * cycle, ... T下面按照“完整行程”計(jì)數(shù)一次行程不只包含經(jīng)過(guò)的隧道也包含每次等待之后選擇的出發(fā)時(shí)刻。因此即使經(jīng)過(guò)的節(jié)點(diǎn)序列相同只要等待安排不同產(chǎn)生的狀態(tài)轉(zhuǎn)移序列也不同代碼會(huì)把它們分別保留。這個(gè)口徑也解釋了為什么不能只為一條邊保留最近的開放時(shí)刻如果只按邊序列區(qū)分路徑則還需要另外去重。在展開后的狀態(tài)圖上所有轉(zhuǎn)移代價(jià)都是wait cost并且嚴(yán)格大于 0因此仍然可以使用類似 Dijkstra 的小根堆。used[u][p]不表示這個(gè)狀態(tài)是否訪問(wèn)過(guò)而是記錄狀態(tài)(u,p)已經(jīng)第幾次有效出隊(duì)。相同狀態(tài)最多擴(kuò)展 K1 次如果它已經(jīng)有 K1 種耗時(shí)不大于當(dāng)前方案的到達(dá)方式那么后面的任意一段走法都可以分別接在這 K1 個(gè)前綴之后當(dāng)前方案不可能再影響終點(diǎn)的前 K1 個(gè)答案。當(dāng)終點(diǎn)第 K1 次出隊(duì)時(shí)當(dāng)前總時(shí)間就是答案。代碼還在反圖上做了一次普通 BFS提前標(biāo)記哪些節(jié)點(diǎn)在拓?fù)渖夏軌虻竭_(dá)終點(diǎn)不能到達(dá)終點(diǎn)的分支無(wú)需進(jìn)入優(yōu)先隊(duì)列。完整代碼如下#include bits/stdc.h using namespace std; ? typedef long long ll; ? struct Edge { int to; int cycle; int cost; }; struct State { ll dist; // 從 0 號(hào)星球出發(fā)所用的總時(shí)間 int node; // 當(dāng)前星球 int phase; // 當(dāng)前時(shí)間模所有周期的最小公倍數(shù) ? bool operator(const State other) const { if (dist ! other.dist) return dist other.dist; if (node ! other.node) return node other.node; return phase other.phase; } }; ? int gcd_int(int a, int b) { while (b ! 0) { int r a % b; a b; b r; } return a; } ? int main() { ios::sync_with_stdio(false); cin.tie(NULL); ? int N, M, K, T; int caseNo 1; ? while (cin N M K T) { if (N 0 M 0 K 0 T 0) { break; } ? vectorvectorEdge graph(N); vectorvectorint reverseGraph(N); int period 1; ? for (int i 0; i M; i) { int u, v, c, w; cin u v c w; ? graph[u].push_back(Edge{v, c, w}); reverseGraph[v].push_back(u); ? period period / gcd_int(period, c) * c; } ? vectorbool canReachTarget(N, false); queueint q; ? const int target N - 1; canReachTarget[target] true; q.push(target); ? while (!q.empty()) { int u q.front(); q.pop(); ? for (size_t i 0; i reverseGraph[u].size(); i) { int v reverseGraph[u][i]; if (!canReachTarget[v]) { canReachTarget[v] true; q.push(v); } } } ? const int need K 1; ll answer -1; ? if (canReachTarget[0]) { // used[u][p]狀態(tài) (u,p) 已經(jīng)從優(yōu)先隊(duì)列中彈出的次數(shù) vectorvectorint used(N, vectorint(period, 0)); ? priority_queueState, vectorState, greaterState pq; pq.push(State{0, 0, 0}); ? int reachedTarget 0; ? while (!pq.empty()) { State cur pq.top(); pq.pop(); // 前 need 次以后到達(dá)同一狀態(tài)的路徑不可能影響答案 if (used[cur.node][cur.phase] need) { continue; } used[cur.node][cur.phase]; ? if (cur.node target) { reachedTarget; ? if (reachedTarget need) { answer cur.dist; break; } } ? for (size_t i 0; i graph[cur.node].size(); i) { const Edge e graph[cur.node][i]; ? if (!canReachTarget[e.to]) { continue; } ? int rem cur.phase % e.cycle; int firstWait (e.cycle - rem) % e.cycle; for (int wait firstWait; wait T; wait e.cycle) { ? ll nextDist cur.dist wait e.cost; int nextPhase (cur.phase wait e.cost) % period; ? if (used[e.to][nextPhase] need) { pq.push(State{nextDist, e.to, nextPhase}); } } } } } ? cout Case caseNo : answer \n; } ? return 0; }這份代碼之中需要注意下面幾個(gè)細(xì)節(jié)period period / gcd_int(period, c) * c逐步計(jì)算所有隧道周期的最小公倍數(shù)。因?yàn)槊總€(gè)c都不超過(guò) 10所以period最大只有 2520不會(huì)出現(xiàn)狀態(tài)數(shù)量無(wú)限增長(zhǎng)的問(wèn)題。nextPhase可以直接通過(guò)(cur.phase wait e.cost) % period計(jì)算。雖然cur.phase不是完整的絕對(duì)時(shí)間但是所有邊的周期都整除period因此保留這個(gè)余數(shù)已經(jīng)足夠決定后續(xù)所有等待時(shí)間。used[u][p]必須在狀態(tài)出隊(duì)時(shí)增加而不是在入隊(duì)時(shí)增加。優(yōu)先隊(duì)列保證出隊(duì)順序按照總時(shí)間遞增若在入隊(duì)時(shí)就計(jì)數(shù)后加入但距離更短的合法狀態(tài)可能會(huì)被過(guò)早剪掉。優(yōu)先隊(duì)列中可能存在dist、node、phase完全相同的多個(gè)狀態(tài)這里不能像普通最短路那樣去重。它們可能由不同的路徑或者不同的隧道產(chǎn)生而題目要求這些走法分別計(jì)數(shù)。canReachTarget只根據(jù)圖的連通關(guān)系進(jìn)行剪枝。它為false時(shí)一定無(wú)法到達(dá)終點(diǎn)為true只表示拓?fù)渖洗嬖诼窂讲⒉槐ＷC在等待上限之內(nèi)一定可行真正的時(shí)間約束仍然要在狀態(tài)轉(zhuǎn)移時(shí)判斷。題目給的是追兵數(shù)量 K要求的是第 K1 短路徑所以代碼使用need K 1。這一點(diǎn)和第二、三部分直接輸入“第 K 條”并不一樣。單條隧道的通過(guò)時(shí)間可達(dá) 10^6路徑又允許繞環(huán)所以總時(shí)間使用long long存儲(chǔ)。令 L 為所有周期的最小公倍數(shù)RK1。對(duì)于一條周期為 C_e 的邊在一個(gè)時(shí)間相位下最多產(chǎn)生 \lfloor T/C_e\rfloor1 種等待方案。如果把展開圖的邊數(shù)記為令 L 為所有周期的最小公倍數(shù)RK1。對(duì)于一條周期為 Ce 的邊在一個(gè)時(shí)間相位下最多產(chǎn)生 ?T/Ce?1 種等待方案。如果把展開圖的邊數(shù)記為/ppE ≤ L·Σsube∈E/sub(?T/Csube/sub?1)/pp那么多次出隊(duì) Dijkstra 的時(shí)間復(fù)雜度可以寫成 O(RE·log(RE))。used數(shù)組的空間復(fù)雜度為 O(NL)如果把優(yōu)先隊(duì)列中的狀態(tài)也計(jì)算在內(nèi)最壞空間可以寫成 O(NLRE)。代碼在狀態(tài)出隊(duì)時(shí)現(xiàn)場(chǎng)枚舉轉(zhuǎn)移因此不需要顯式建出整張展開圖。這個(gè)上界比較松實(shí)際產(chǎn)生的候選狀態(tài)數(shù)量仍然取決于圖的結(jié)構(gòu)。五、總結(jié)最后把本文幾種容易混淆的模型放在一起比較問(wèn)題類型路徑是否允許重復(fù)節(jié)點(diǎn)狀態(tài)中需要保留什么適合的做法單源最短路不作限制最短解可取簡(jiǎn)單路徑當(dāng)前節(jié)點(diǎn)Dijkstra第 K 短游走允許當(dāng)前節(jié)點(diǎn)、到達(dá)次數(shù)反向 Dijkstra 計(jì)算啟發(fā)函數(shù)再用 A* 多次擴(kuò)展第 K 短簡(jiǎn)單路徑不允許完整路徑前綴與偏離位置Yen 算法 受限最短路帶周期等待的第 K 短游走允許當(dāng)前節(jié)點(diǎn)、時(shí)間相位、到達(dá)次數(shù)狀態(tài)展開 多次出隊(duì)的 Dijkstra所以遇到“第 K 短路”時(shí)第一件事不是直接套模板而是先確認(rèn)題目中的“路徑”到底是什么能不能重復(fù)經(jīng)過(guò)節(jié)點(diǎn)和邊相同長(zhǎng)度的不同走法是否分別計(jì)數(shù)邊權(quán)是否會(huì)隨狀態(tài)或時(shí)間變化。把這幾個(gè)問(wèn)題區(qū)分清楚之后應(yīng)該使用 A*、Yen還是狀態(tài)展開通常也就比較明確了。