Dijkstra算法來計算從給定的源點s爲O的最短路徑（（V + E）日誌W）時間

Question

G（V，E）是加權，針對具有非負權重函數W圖表：電子 - > {0,1,2,3,4 ... W}其中W是任何非負整數。我想修改Dijkstra算法計算從給定的源點s爲O的最短路徑（（V + E）登錄W）的時間。

Answer 1

讓我們標準的Dijkstra算法優先級隊列，並且改變它一點點：

1. 我們必須從一個int（距離）的矢量的地圖，以保持與所有的頂點給定的距離。

2. 我們會從第一向量流行元素，以獲得在每次迭代當前頂點和刪除鍵，如果矢量變空。

3. ，當我們把它添加到隊列中，我們會推一個元素到相應的載體。

有在地圖上的任何一點至多W + 1不同的密鑰。爲什麼？讓v是當前頂點和d[v]是它的距離。所有小於d[v]的密鑰都被刪除。任何未發現的頂點不在地圖中。對於任何發現的頂點ud[u] <= d[v] + max_edge_lenght = d[v] + W。因此，地圖中的任何鍵必須位於[d[v], d[v] + W]範圍內。

地圖的大小爲O(W)，所以每個作品在O(log W)時間（推送/彈出矢量元素爲O(1)）。

當然，只有當W相對較小時纔有用（否則，您可以使用標準的O((V + E) log V)實現）。