Dijkstra 和反向 Dijkstra 到底分別在什么場景下使用圖中的第 K 短路徑要怎么找如果允許重復(fù)經(jīng)過節(jié)點(diǎn)或者要求路徑不能重復(fù)經(jīng)過節(jié)點(diǎn)處理方式有什么不同當(dāng)路徑還帶有等待時(shí)間約束時(shí)算法又該如何改造本文會通過四類題型由淺入深地講解這些問題。一、標(biāo)準(zhǔn) Dijkstra 算法的描述和應(yīng)用Dijkstra 算法是用來求解非負(fù)權(quán)圖上的單源最短路徑問題的經(jīng)典方法從一個(gè)源點(diǎn)出發(fā)求它到圖中其余節(jié)點(diǎn)的最短距離。有向圖和無向圖都可以使用但只要存在負(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)行過程之中這個(gè)值可能經(jīng)過多次松弛而逐漸變小?？梢园?Dijkstra 類比成將普通 BFS 的先進(jìn)先出隊(duì)列換成按照當(dāng)前路徑長度排序的優(yōu)先隊(duì)列更準(zhǔn)確地說它每次選取暫定距離最小的狀態(tài)(distance, u)再遍歷u的所有鄰邊。如果經(jīng)過u能讓相鄰節(jié)點(diǎn)v的距離變得更小就更新dist[v]這一過程稱為松弛。由于所有邊權(quán)都非負(fù)一個(gè)沒有過期的狀態(tài)從堆頂彈出時(shí)對應(yīng)節(jié)點(diǎn)的最短距離就可以確定下來。先以 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則表示二者之間沒有直接連接。節(jié)點(diǎn)向自身發(fā)送消息不需要網(wǎng)絡(luò)傳輸因此 A(i,i)0。網(wǎng)絡(luò)為無向圖滿足 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 號處理器向所有其他處理器廣播消息所需的最短時(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); //鄰接表方式存儲圖 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)編號。graph[i]存放所有從節(jié)點(diǎn)i出發(fā)的邊無向邊需要分別加入兩個(gè)方向。有向圖和無向圖都可以使用鄰接表只是加邊方式不同。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)編號}隊(duì)列先比較距離距離相同時(shí)再比較節(jié)點(diǎn)編號。Dijkstra 真正依賴的是距離較小的狀態(tài)先出隊(duì)節(jié)點(diǎn)編號只負(fù)責(zé)在距離相同時(shí)確定一個(gè)穩(wěn)定的先后順序不會影響最短距離的正確性。for (const auto e : graph[u])遍歷節(jié)點(diǎn)u的所有鄰邊。若distance e.w dist[v]說明經(jīng)過u到達(dá)v更短此時(shí)更新dist[v]并把新狀態(tài)加入優(yōu)先隊(duì)列。if (distance ! dist[u]) continue;用來跳過過期狀態(tài)。比如隊(duì)列中先后出現(xiàn){10,u}和{7,u}當(dāng){10,u}出隊(duì)時(shí)dist[u]已經(jīng)被更新為 7那么距離 10 的狀態(tài)就沒有繼續(xù)擴(kuò)展的必要。這里不是說節(jié)點(diǎn)u只能處理一次而是只處理與當(dāng)前最優(yōu)記錄一致的狀態(tài)。在絕大多數(shù)稀疏圖中鄰接表加小根優(yōu)先隊(duì)列都是最常用也最穩(wěn)妥的實(shí)現(xiàn)。采用上面這種允許同一節(jié)點(diǎn)多次入堆、出隊(duì)時(shí)跳過舊狀態(tài)的寫法時(shí)堆中最多可能出現(xiàn) O(E) 個(gè)狀態(tài)因此也可以把復(fù)雜度寫成 O((VE)log E)。對于普通簡單圖E ≤ V2所以通常簡寫為 O((VE)log V)?？臻g復(fù)雜度為 O(VE)。鄰接表加優(yōu)先隊(duì)列屬于堆優(yōu)化 Dijkstra尤其適合邊數(shù)遠(yuǎn)小于 V2 的稀疏圖。為了對照另一種寫法接下來看 POJ 2387 - Til the Cows Come Home。題目給定一個(gè)正權(quán)無向圖節(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)編號第三個(gè)整數(shù)表示道路長度范圍1到100輸出格式一個(gè)整數(shù)表示貝茜從 V 號地標(biāo)到 1 號地標(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í)同一對節(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í)無法到達(dá)。每一輪通過線性掃描找到一個(gè)尚未確定、且dist最小的節(jié)點(diǎn)u再用dist[u] graph[u][v]松弛其他節(jié)點(diǎn)。由于邊權(quán)非負(fù)u被選中之后它的最短距離就可以確定下來。上述代碼展示的是 Dijkstra 的樸素實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(V^2)空間復(fù)雜度也是 O(V^2)。需要說明的是POJ 2387 本身只有至多 2000 條邊實(shí)際上屬于稀疏圖使用鄰接表加優(yōu)先隊(duì)列會更合適這里只是借它規(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ì)列中取出。對于正權(quán)圖第 1 次取出節(jié)點(diǎn)u對應(yīng)到達(dá)u的最短路徑第 2 次對應(yīng)第二短依次類推。這個(gè)方法能夠求允許重復(fù)經(jīng)過節(jié)點(diǎn)和邊的第 K 短路但如果直接按照已經(jīng)走過的距離擴(kuò)展優(yōu)先隊(duì)列中會出現(xiàn)大量最終到不了終點(diǎn)、或者明顯偏離終點(diǎn)的狀態(tài)。A* 的作用就是利用“距離終點(diǎn)還剩多遠(yuǎn)”來調(diào)整擴(kuò)展順序盡量少搜索無關(guān)區(qū)域。下面以 POJ 2449 - Remmarguts Date 為例。題目大意是在有向正權(quán)圖中求從起點(diǎn) S 到終點(diǎn) T 的第 K 短路徑長度。路徑允許重復(fù)經(jīng)過節(jié)點(diǎn)和邊長度相同但經(jīng)過方式不同的路徑也分別計(jì)數(shù)如果不存在第 K 短路徑則輸出-1。輸入格式第一行包含兩個(gè)整數(shù)N和M1 ≤ N ≤ 10000 ≤ M ≤ 1000000。站點(diǎn)編號從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 短路徑的長度不存在則輸出-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)因此會優(yōu)先擴(kuò)展更有希望較早到達(dá)終點(diǎn)的狀態(tài)。A* 會給每個(gè)待搜索狀態(tài)計(jì)算評價(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ò)展的無效節(jié)點(diǎn)也就越少。也就是需要滿足以下兩個(gè)條件可容許性對任意節(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*找到的是真正的最短路徑。一致性對于任意邊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í)最短距離。也就是說這里的h(n)不是大概估計(jì)而是一個(gè)精確的啟發(fā)函數(shù)。為什么要建反圖原圖中的邊是u - v反圖中就存成v - u。從終點(diǎn) T 在反圖上運(yùn)行 Dijkstra得到的h[u]恰好就是原圖中從u到 T 的最短距離。若h[u]為無窮大說明從u根本無法到達(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)走過的實(shí)際距離g、預(yù)計(jì)經(jīng)過終點(diǎn)時(shí)的總距離fgh放在一起。重載之后小根堆會優(yōu)先取出f較小的狀態(tài)若f相同再優(yōu)先取出g較小的狀態(tài)。建圖時(shí)同時(shí)保存原圖和反圖。反向 Dijkstra 得到的h[i]表示原圖中從節(jié)點(diǎn)i到終點(diǎn)的真實(shí)最短距離。它不僅給 A* 提供搜索方向也可以提前過濾h[v] INF的節(jié)點(diǎn)因?yàn)檫@些節(jié)點(diǎn)無論如何都無法走到終點(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擴(kuò)展而終點(diǎn)處滿足h[target]0所以終點(diǎn)第 K 次出隊(duì)時(shí)對應(yīng)的g就是第 K 短路徑長度。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]}會先把長度為 0 的空路徑算作一次到達(dá)。但原題要求的是實(shí)際經(jīng)過邊的路徑所以代碼中需要先執(zhí)行k把空路徑跳過去。這里用反向 Dijkstra 求出的h[i]是精確最短距離不是估計(jì)值。它同時(shí)滿足可容許性和一致性因此 A* 不僅能保證找到第 K 短路而且每個(gè)狀態(tài)第一次出隊(duì)時(shí)就是該節(jié)點(diǎn)在當(dāng)前 g 下的最優(yōu)擴(kuò)展順序。如果換成一個(gè)粗糙的估計(jì)函數(shù)雖然也可能正確但搜索效率會明顯下降。這里求的是允許重復(fù)節(jié)點(diǎn)和邊的第 K 短“游走”只是競賽題中通常仍然簡稱為第 K 短路。不同路徑即使長度相同也要分別計(jì)數(shù)所以優(yōu)先隊(duì)列中的重復(fù)狀態(tài)不能簡單去重。反向 Dijkstra 的復(fù)雜度為 O((NM)\log N)A* 階段中每個(gè)節(jié)點(diǎn)最多有效擴(kuò)展 K 次粗略上界可以寫成 O(KM\log(KM))。啟發(fā)函數(shù)主要減少實(shí)際擴(kuò)展的無關(guān)狀態(tài)但不會改變這里給出的最壞復(fù)雜度上界。三、Yen 算法思想和第 K 短簡單路徑上一道題允許重復(fù)經(jīng)過節(jié)點(diǎn)和邊因此同一個(gè)節(jié)點(diǎn)可以被多次擴(kuò)展。但是如果題目要求路徑中不能重復(fù)經(jīng)過節(jié)點(diǎn)這種“統(tǒng)計(jì)終點(diǎn)第幾次出隊(duì)”的方法就不能直接使用了。下面介紹 UVa 1685 - Enjoyable Commutation這道題要求的正是第 K 短簡單路徑。題目給定一個(gè)帶正權(quán)的有向圖需要求從起點(diǎn) a 到終點(diǎn) b 的第 K 短路徑滿足一條路徑不能重復(fù)經(jīng)過同一個(gè)節(jié)點(diǎn)也就是必須是簡單路徑先按照路徑總長度從小到大排序如果兩條路徑長度相同再按照節(jié)點(diǎn)序列的字典序排序如果不足 K 條路徑輸出None否則用連字符輸出第 K 條路徑經(jīng)過的節(jié)點(diǎn)。每組數(shù)據(jù)的第一行包含n m k a b其中 2 \leq n \leq 501 \leq k \leq 200。接下來的 m 行每行給出一條有向邊x y d。題目保證不存在自環(huán)同一對有序節(jié)點(diǎn)之間也不會出現(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 算法先求出第一短的簡單路徑然后依次構(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)的后半段。為了讓新路徑既不同于已有答案又仍然是簡單路徑需要做兩類限制禁止rootPath中偏離點(diǎn)之前的所有節(jié)點(diǎn)防止后半段繞回前綴并重復(fù)經(jīng)過節(jié)點(diǎn)對所有與當(dāng)前rootPath前綴相同的已有答案禁止它們在偏離點(diǎn)之后使用的那條邊防止重新生成已經(jīng)確定的路徑。每個(gè)偏離點(diǎn)都可能產(chǎn)生一條候選路徑這些候選不能在本輪結(jié)束后丟掉因?yàn)榈谝粭l路徑產(chǎn)生的某個(gè)候選也可能直到第五輪才成為最優(yōu)答案。所以代碼使用一個(gè)全局候選集合candidates按照“總長度、節(jié)點(diǎn)序列字典序”排序。每一輪從中取出最小者作為下一條正式答案。還需要解決一個(gè)子問題在刪除部分節(jié)點(diǎn)和邊之后如何找到長度最短、且字典序最小的路徑這里先在反圖上從終點(diǎn)執(zhí)行 Dijkstra得到dist[u]表示節(jié)點(diǎn)u到終點(diǎn)的最短距離。然后從起點(diǎn)正向恢復(fù)路徑每一步在所有滿足dist[u] w(u,v) dist[v]的鄰邊中選擇終點(diǎn)編號最小的一個(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; // 路徑總長度 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 對應(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)編號升序排列。 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 自動按照題目要求排序并且自動去重。 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)的前綴長度。 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ù)訪問節(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í)沒有入選的路徑會一直保留這正是 Yen 算法不能缺少的候選池。bannedNode只禁止根路徑中spurNode之前的節(jié)點(diǎn)不禁止偏離點(diǎn)本身。否則無法從偏離點(diǎn)出發(fā)尋找新的后綴如果完全不禁前綴節(jié)點(diǎn)新后綴又可能繞回前面生成帶重復(fù)節(jié)點(diǎn)的路徑。bannedEdge需要檢查所有已經(jīng)進(jìn)入answers的路徑。只禁止上一條答案使用的邊是不夠的否則可能重新生成更早已經(jīng)出現(xiàn)過的路徑。shortestPath每次都在當(dāng)前的禁點(diǎn)、禁邊條件下重新求最短路。由于原題邊權(quán)嚴(yán)格為正根據(jù)dist恢復(fù)路徑時(shí)不會陷入零權(quán)環(huán)同時(shí)題目保證同一對有序節(jié)點(diǎn)之間至多一條邊所以可以直接使用(u,v)表示一條被禁用的邊并使用weightEdge[u][v]計(jì)算前綴長度。Yen 算法正確性的關(guān)鍵就在“第一次偏離”上。任意一條尚未進(jìn)入答案集合的簡單路徑與某一條已有路徑相比都可以找到第一個(gè)不同的邊。枚舉已有路徑上的每個(gè)偏離點(diǎn)就不會漏掉它可能對應(yīng)的候選而每次從全局候選池中取出排序最小的路徑又保證了新加入answers的確實(shí)是下一條路徑。一次shortestPath主要執(zhí)行一次堆優(yōu)化 Dijkstra復(fù)雜度約為 O((NM)\log N)。一條簡單路徑最多包含 N 個(gè)節(jié)點(diǎn)生成一條新答案時(shí)最多調(diào)用 O(N) 次最短路所以核心復(fù)雜度可以粗略寫成 O(KN(NM)\log N)。當(dāng)前代碼為了判斷相同前綴還會直接掃描已有答案最壞會額外產(chǎn)生 O(K^2N^2) 的前綴比較候選路徑本身最多占用 O(KN^2) 的空間。在本題 N \leq 50、K \leq 200 的范圍內(nèi)這樣的寫法更直觀也足以應(yīng)對數(shù)據(jù)范圍。四、另一種 K 短路允許重復(fù)經(jīng)過節(jié)點(diǎn)并帶有等待約束第二部分的 POJ 2449 已經(jīng)允許重復(fù)經(jīng)過節(jié)點(diǎn)和邊這一部分真正增加的難點(diǎn)不是“允許重復(fù)”而是邊的代價(jià)會隨到達(dá)時(shí)間發(fā)生變化。下面以 UVa 1684 - Escape Plan 為例。題目中有 N 個(gè)星球編號為 0 到 N-1其中 0 是起點(diǎn)N-1 是終點(diǎn)。星球之間存在單向的超空間隧道每條隧道由四個(gè)整數(shù)U V C W描述隧道從U指向V通過隧道需要花費(fèi)W秒隧道只會在時(shí)間 0,C,2C,3C,\dots 開放在任意一個(gè)星球上連續(xù)等待的時(shí)間不能超過T秒。有 K 艘帝國殲星艦會沿著較短的路線追擊因此需要求從 0 到 N-1 的第 K1 短路徑。路徑允許重復(fù)經(jīng)過節(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通過隧道的時(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)就會丟失必要的信息。比如同樣到達(dá)節(jié)點(diǎn)u到達(dá)時(shí)間分別為 8 和 9面對一條每 3 秒開放一次的隧道接下來需要等待的時(shí)間并不相同。因此這里需要把狀態(tài)寫成(node, phase)其中phase是當(dāng)前總時(shí)間對所有隧道周期最小公倍數(shù)的余數(shù)。因?yàn)?1 \leq C \leq 10所有周期的最小公倍數(shù)最多為lcm(1,2,...,10) 2520只要兩個(gè)到達(dá)時(shí)間模period相同它們面對每一條隧道時(shí)的開放情況就完全相同。這樣一來原本隨絕對時(shí)間變化的問題就被展開成了至多 N \times 2520 個(gè)有限狀態(tài)。假設(shè)當(dāng)前時(shí)間對周期的余數(shù)為phase準(zhǔn)備經(jīng)過周期為cycle的邊。距離最近一次可出發(fā)時(shí)間還需要等待int firstWait (cycle - phase % cycle) % cycle;但是不能只考慮最近的一次開放。如果firstWait cycle、firstWait 2 * cycle仍然不超過T主動多等一段時(shí)間也是合法選擇并且可能影響后續(xù)邊的開放時(shí)刻。所以代碼需要枚舉firstWait, firstWait cycle, firstWait 2 * cycle, ... T下面按照“完整行程”計(jì)數(shù)一次行程不只包含經(jīng)過的隧道也包含每次等待之后選擇的出發(fā)時(shí)刻。因此即使經(jīng)過的節(jié)點(diǎn)序列相同只要等待安排不同產(chǎn)生的狀態(tài)轉(zhuǎn)移序列也不同代碼會把它們分別保留。這個(gè)口徑也解釋了為什么不能只為一條邊保留最近的開放時(shí)刻如果只按邊序列區(qū)分路徑則還需要另外去重。在展開后的狀態(tài)圖上所有轉(zhuǎn)移代價(jià)都是wait cost并且嚴(yán)格大于 0因此仍然可以使用類似 Dijkstra 的小根堆。used[u][p]不表示這個(gè)狀態(tài)是否訪問過而是記錄狀態(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)的分支無需進(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 號星球出發(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都不超過 10所以period最大只有 2520不會出現(xiàn)狀態(tài)數(shù)量無限增長的問題。nextPhase可以直接通過(cur.phase wait e.cost) % period計(jì)算。雖然cur.phase不是完整的絕對時(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)可能會被過早剪掉。優(yōu)先隊(duì)列中可能存在dist、node、phase完全相同的多個(gè)狀態(tài)這里不能像普通最短路那樣去重。它們可能由不同的路徑或者不同的隧道產(chǎn)生而題目要求這些走法分別計(jì)數(shù)。canReachTarget只根據(jù)圖的連通關(guān)系進(jìn)行剪枝。它為false時(shí)一定無法到達(dá)終點(diǎn)為true只表示拓?fù)渖洗嬖诼窂讲⒉槐ＷC在等待上限之內(nèi)一定可行真正的時(shí)間約束仍然要在狀態(tài)轉(zhuǎn)移時(shí)判斷。題目給的是追兵數(shù)量 K要求的是第 K1 短路徑所以代碼使用need K 1。這一點(diǎn)和第二、三部分直接輸入“第 K 條”并不一樣。單條隧道的通過時(shí)間可達(dá) 10^6路徑又允許繞環(huán)所以總時(shí)間使用long long存儲。令 L 為所有周期的最小公倍數(shù)RK1。對于一條周期為 C_e 的邊在一個(gè)時(shí)間相位下最多產(chǎn)生 \lfloor T/C_e\rfloor1 種等待方案。如果把展開圖的邊數(shù)記為令 L 為所有周期的最小公倍數(shù)RK1。對于一條周期為 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)場枚舉轉(zhuǎn)移因此不需要顯式建出整張展開圖。這個(gè)上界比較松實(shí)際產(chǎn)生的候選狀態(tài)數(shù)量仍然取決于圖的結(jié)構(gòu)。五、總結(jié)最后把本文幾種容易混淆的模型放在一起比較問題類型路徑是否允許重復(fù)節(jié)點(diǎn)狀態(tài)中需要保留什么適合的做法單源最短路不作限制最短解可取簡單路徑當(dāng)前節(jié)點(diǎn)Dijkstra第 K 短游走允許當(dāng)前節(jié)點(diǎn)、到達(dá)次數(shù)反向 Dijkstra 計(jì)算啟發(fā)函數(shù)再用 A* 多次擴(kuò)展第 K 短簡單路徑不允許完整路徑前綴與偏離位置Yen 算法 受限最短路帶周期等待的第 K 短游走允許當(dāng)前節(jié)點(diǎn)、時(shí)間相位、到達(dá)次數(shù)狀態(tài)展開 多次出隊(duì)的 Dijkstra所以遇到“第 K 短路”時(shí)第一件事不是直接套模板而是先確認(rèn)題目中的“路徑”到底是什么能不能重復(fù)經(jīng)過節(jié)點(diǎn)和邊相同長度的不同走法是否分別計(jì)數(shù)邊權(quán)是否會隨狀態(tài)或時(shí)間變化。把這幾個(gè)問題區(qū)分清楚之后應(yīng)該使用 A*、Yen還是狀態(tài)展開通常也就比較明確了。