應用程序搜索鐵路連接

Question

我正在管理一個項目，可以描述如下。

應用程序應顯示從A市到B市的列車連接，並根據總行程時間，總公里數，車站等候時間等進行優化。它有更多的要求，但它們並不那麼難以處理單獨。

我希望收到實施建議。我在考慮城市是頂點和鐵路是邊緣的間接圖。每條鐵路都有起點城市，終點城市，長度和其他參數。

主要問題如下：在一個數據庫中會有指定的起點站，終點站和中間站，並有給定的到達和離開時間。 你會提出什麼算法能夠找到從A城市到B城市的最佳連接？

我在想以下內容：將有矩陣的維數A[n][n]，其中n是城市數量。假設a和b是城市A和B的ID。如果存在從A到B的直接火車，A[a][b]=1，否則A[a][b]=0。如果不存在這樣的中心，系統試圖通過與A連接的城市和B連接來尋找連接。它是否是有效的解決方案？

Answer 1

爲每個軌道段創建邊緣，以便可以爲連接點和邊線等建模。節點將這些邊緣中的每一個組合在一起，它們不需要僅僅是站點。

然後讓自己boost :: graph和使用它的一個算法來爲你做所有的辛苦工作:)建議的是A *或Dijkstra。