我正在一個Java項目上，除其他事項外，該項目需要使用最大停止數(shù)返回從x到y(tǒng)的所有可能路徑。例如，每個節(jié)點都是一個城市，從一個城市到另一個城市的每條路徑都具有成本值。我正在通過參考使用本文，這是我使用的相同模型。 http://www.vogella.com/tutorials/JavaAlgorithmsDijkstra/article.html將最短的路徑從x返回到Y(jié)可以正常工作，但是我需要每種路徑的所有可能路徑和成本。例如：在給定的最大停靠點數(shù)內(nèi)查找來自任何給定的一對城鎮(zhèn)的所有可用路線。輸入圖：AB5，BC4，CD8，DC8，DE6，AD5，CE2，EB3，AE7從C到C的路線，最多3站：CDC（2站）CEBC（3站）從A到C的路線，最多4站：ABC（2停）ADC（2停）AEBC（3停）ADEBC（4停）
2 回答
慕哥9229398
TA貢獻1877條經(jīng)驗 獲得超6個贊
老實說，我會用BFS代替Dijkstra。您不是在尋找最短路徑，而是任何路徑。因此，您可以只在節(jié)點x上運行BFS，然后執(zhí)行k步（我將最大步數(shù)稱為k）即可停止它。每次到達y時，都可以將路徑添加到答案中。
catspeake
TA貢獻1111條經(jīng)驗 獲得超0個贊
每個節(jié)點鏈接的權(quán)重就是兩者之間的距離。
例如）A-> 7-> B-> 3 ---> C --->等等...
在這種情況下，從A到C的路徑的總權(quán)重將是每個坐標之間所有權(quán)重（距離）的總和。
低于最大值的所有可能路徑都可以通過上述計算方式記錄下來
添加回答
舉報
0/150
提交
取消