Dag的最短路徑

Question

我有一個s和t頂點的圖，我需要找到兩者之間的最短路徑。該圖有很多我想要利用的特殊屬性：

• 該圖是一個DAG（有向無環圖）。
• 我可以在O（| V |）時間內創建一個拓撲排序，比傳統的O（| V + E |）更快。
• 在拓撲排序中，s是列表中的第一項，t是最後一項。

有人告訴我，一旦我有一個拓撲排序的頂點，我能找到的最短路徑比我目前的Dijkstra的統一成本標準快，但我似乎無法找到它的算法。

僞代碼將不勝感激。

EDITS： 從s到t的所有路徑都有相同的邊數。 邊緣有重量。 我正在尋找最低成本的路徑。

Answer 1

我要違揹我的直覺，並認爲這不是作業。你必須利用拓撲排序給你的信息。每當你以拓撲順序檢查節點n時，你都可以保證你已經遍歷了每條可能的路徑。使用這種很明顯地看到，您可以用拓撲排序（僞）的一個線性掃描生成的最短路徑：

Graph g 
Source s 
top_sorted_list = top_sort(g) 

cost = {} // A mapping between a node, the cost of its shortest path, and 
      //its parent in the shortest path 

for each vertex v in top_sorted_list: 
    cost[vertex].cost = inf 
    cost[vertex].parent = None 

cost[s] = 0 

for each vertex v in top_sorted_list: 
    for each edge e in adjacensies of v: 
     if cost[e.dest].cost > cost[v].cost + e.weight: 
     cost[e.dest].cost = cost[v].cost + e.weight 
     e.dest.parent = v 

現在你可以從s查找任何最短路徑到目的地。您只需要在成本映射中查找目的地，獲取它的父級，然後重複此過程，直到獲得父級爲s的節點，然後您擁有最短路徑。