通過選擇每個級別上最強連接節點的有向圖中的最短路徑

Question

我正在尋找在有向圖中找到點A和B之間的路徑的算法。約束是必須總是首先嚐試成本最高的邊。 與查找最短或最長的路徑不同，因爲必須在每個級別檢查此限制。 我將給出爲例：第一列的出發點和所述第二列中的目的地點：

• AC 8
• AD 5
• AE 2
• BA 1
• DA 5
• DB 1
• DE 3
• EB 2

從A到B的正確的路徑將是： A - 5 - > d --1 - >乙 A至C是第一次嘗試，但由於C不連接到任何其它節點它繼續第二個選項：A到D D到A被丟棄，因爲A是當前路徑的一部分（AD） 儘管在D和E之間存在另一個更強的連接，但選擇了D到B來最小化路徑。

所以按重要性順序的約束上有： - 最短路徑 - 在每個級別最強的連接

謝謝， Cristi

Answer 1

這是一個改進的Dijkstra算法，每步偏好重邊。