圖的最短路徑，我有以下情形：查找與動態重
我想找到兩個城市之間的航班：A和B的存在從沒有直飛航班到B;所以，我需要找到一個成本最低的連接航班。
另外，機票沒有固定。這取決於我買它的時間;例如，如果我早點購買，價格會更便宜。
此外，時間也影響飛行;例如，5月31日上午7點從C到D只有一班航班。如果飛機在5月31日上午8點從A飛到C，我錯過了航班。出於這個原因，我將城市表示爲圖的頂點。如果有從A到B的有效航班，則AB路徑存在。重量將是機票費用。
對我的問題有什麼想法或建議嗎？
感謝
我回答曾經是一個非常similar question我敢肯定，同樣的想法可以在這裏使用。這個想法是使用一個路由算法，專爲互聯網路由器 - 這是動態的和不斷變化的。爲其設計的算法是Distance Vector Routing Protocol。
建議的實現基本上是Bellman-Ford算法的分佈式版本，一旦每個邊的權重發生變化就可以修改自身，以便獲得新的最佳路徑。
注意，該算法得出的背影，主要是count to infinity problem。
通常的方式來處理在正確的時間出現在正確的地方並非是使節點表示在特定的時間特定的地點。然後，從C到D的航班將於5月30日晚上9點發車，並於5月31日上午7點到達，相當於從節點C_May30_9PM到D_May31_7AM的一條弧線。您還需要對應於等待的弧線，例如D_May31_7AM到D_May31_8AM。
我不確定在您所描述的細節級別購買門票方面有很多話要說。
聽起來像一個相當簡單的[A *]（http://en.wikipedia.org/wiki/A*）的問題（你會明顯地還必須保持到達每個城市的日期），但不是隻保留通向一個特定城市的最佳路徑，你必須保留所有的路徑（儘管你可以刪除那些後來到達並且比另一條路徑更昂貴的路徑）。 – Dukeling
[相關問題]（http://stackoverflow.com/questions/15938954/is-there-is-a-route-from-city-a-to-city-b-in-no-more-than-x-天），儘管它使天而不是成本最小化。 – Dukeling