油箱的最短路徑

這是一個家庭作業問題，我很樂意提供一些指導。設G =（V，E）爲無向圖，其中每個頂點表示一個城市，並且邊具有代表行進距離的權重。有些城市有加油站。一輛汽車從頂點開始，帶一個油箱，行程長度爲L.我需要找到s和t之間的最短路徑，以便汽車不會耗盡氣體。油箱的最短路徑

我的主要想法是使用Floyd-Warshall算法進行一些更改。當我們計算最短路徑（i，j，0）時，如果我有一個加油站，並且L-w（i，j）> 0，則分配w（i，j），否則分配無窮大。但是，對於接下來的步驟，我不知道如何將當前燃料狀態添加到計算中。

謝謝。

來源

2013-05-21 Roy

如果你會展示[你已經嘗試了什麼]（http://whathaveyoutried.com），這真的會有所幫助，所以我們不會浪費時間提出你已經知道不了的想法。你也許會發現[Jon的博客條目]（http://tinyurl.com/so-hints）有用。 –

@DanPichelman：我的主要想法是使用Floyd-Warshall算法進行一些更改。當我們計算最短路徑（i，j，0）時，如果我有一個加油站並且L-w（i，j）> 0，則分配w（i，j），否則就是infnity。但是，對於接下來的步驟，我不知道如何將當前燃料狀態添加到計算中。 – Roy

我想知道[Dijkstra]（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）可能更適合，因爲你有一個已知的起點和終點。當分析與「下一個節點」的距離時，超過L - 「自上次加油站以來的長度」的任何值都是無窮大。如果當前節點有氣體，則「自上次加油站以來的長度」將重置爲零。（您必須分別跟蹤「自上次加油站後的長度」和「路徑總長度」）。不知道這是否正確 - 我有一段時間沒有這樣做。祝你好運，這聽起來像一個有趣的問題。 –

使用加油站製作具有頂點的新加權圖：s,t和城市（C）。

邊緣：

s-c，與c從C，如果有s和c之間的最短路徑長度爲<= L，
c1-c2，與c1，c2從C，長度爲c1-c2 <= L，
c-t，其中c從C，其中le ngth c-e <= L，
s-t，如果長度爲s-t <= L。

和邊緣權重設置爲長度v1-v2。

此圖上的標準Dijkstra應該返回您在原始圖上尋找的最短路徑的骨架。

當Dijkstra詢問邊界頂點的邊時，有可能「迭代地」創建新圖。類似的，首先創建s-c和s-t邊（和頂點），並且如果有對c1-c2和c-t的需求，則將這些頂點和邊添加到圖中。

來源

2013-05-23 07:28:50 Ante

油箱的最短路徑

回答

相關問題