公交換乘演算法

⑴ 公交換乘演算法（C++）

這個演算法就是這個公交網站的核心。

⑵ 公交2次換乘演算法

呃，我來給你說說。先假設一個情況：你的公交次數卡裡面有10次余額。你拿公交次數卡在8:13第一次刷卡（還剩下8次），那麼在10:13之內的這段時間，你可以在任意一輛接受次數卡的公交車上（除了你在8:13時刷卡的那輛公交車，當然一般不會出現這種情況）再另外刷3次（仍然剩8次）。但是有一個條件：你刷過之後的公交車（注意是公交車，不是公交線路）是不再接受你再次刷次數卡的，這時就要扣你電子錢包裡面的錢，如果沒有電子錢包你就只有投幣。2小時之內你刷卡的次數超過了4次，比如你在8:13刷了一次，在10:13之內，你已經又刷了3次，那麼在10:13之內你仍舊需要轉乘的話就要另外計算次數。比如你在9:55的時候你已經是乘坐了四次，達到了最高次數，那麼轉乘就要重新扣你的次數。9:55時你又轉乘另外一趟公交車刷次數卡，這時就要重新扣你的次數（只剩下6次）。刷卡的原則是次數優先，如果沒有次數就扣電子錢包的錢，如果兩種方式都不能足夠支付你乘車費用，就只能投幣了。轉乘不分普通車和中級車，你在普通車上刷了之後拿到中級車上也是不扣次數，但要計入轉乘次數的記錄。

⑶ 網上可以查到公交路線從一點到另一點的換乘方案，這是用什麼演算法實現的呢

http://www.checi.cn/search_bus.asp?p=1&cid=1&buttons=xl&q=%C1%F9%C0%EF%C7%C5+%CA%D7%B6%BC%CC%E5%D3%FD%D1%A7%D4%BA&k=xl 車次網〉公交查詢，可以按公交線路、公交站點、公交換乘查詢，收錄全國 356 個城市公交情況。

⑷ 公共交通線路的搜索是如何實現的簡稱公交換乘演算法

最核心的演算法正是所謂的最短路徑演算法，這個比較簡單
但是 要把演算法用到公交換乘這個裡面去 數據的組織准備 程序效率優化 特殊情形考慮等 是相當地有工作量的

⑸ 求公交換乘演算法程序

用一個鄰接表有向圖來表示一個公交系統
如果乘坐某輛公交車能從站點u到達站點v而不需要換線、調頭，那麼添加一條有向邊e=(u,v)，並且在邊e上附加信息：從u到v的距離（即該邊的權值）、該邊所屬的公交車編號、該邊在該公交線路的哪個方向上（因為有可能同一條公交線路兩個方向經過不同的站點）
之所以用鄰接表是因為這樣的圖是有重邊的
當查詢從節點i到節點j的換乘線路時，用dijkstra找出i和j之間的最短路徑，那麼根據這條路徑上的邊的附加信息就知道要怎麼換乘了
另外，如果需要知道路徑最短的基礎上怎樣換乘的次數最少（也就是在上述的圖中經過的邊數最少），可對dijkstra作少量調整，對於圖中的每個點u，除了記錄當前找到的到該點的最短距離dis[u]以及該點的前趨pi[u]，還要記錄在這樣的最短距離和前趨下從起點到該點經過的最少的邊數min_edge[u]
那麼作dijkstra的時候，對於當前剛找到的路徑最短的點u，以及從點u出發的某條邊e=(u,v)，如果dis[u]+e.length==dis[v]
&&
min_edge[u]+1<min_edge[v]（也就是經過邊(u,v)與原先的到v的最短路徑長度相同但是經過(u,v)可以得到邊數更少的路徑，那麼也要採用(u,v)）
回溯是效率非常低的演算法，如果沒有非常好的優化方案，沒事少用