Coldwings2015-07-04 07:51:28

我的做法是：將每一趟公交路線上每一對節點連一條有向邊，並記錄時間及車次；使用前向星/邊表/出邊表而不是臨接矩陣儲存。對，就是答主所說“異常麻煩”的方法。

只是真的不麻煩啊……保證一個換乘線路里連續的邊車次不同就行了，求最短求路線求最少換乘路線求所有路線求次短三短第k短路線都可以直接用此圖。跟所謂“普通圖”用法比起來不過是多個判斷而已……

知乎使用者2015-07-04 10:07:40

以帶時刻表的火車線路查詢為例，介紹圖的設計，不帶時刻表的話會簡單很多

節點結構：包含時間和地點兩個資訊（以及節點/地點型別），比如5：00在地點（經緯度）X，6：00在A車站門口，6：30在火車上B站

節點型別可能包括：任意的座標XY，車站前，火車上某站

連線結構：包含起始節點，終結節點，費用（以及連線型別）

連線型別可能包括：從座標XY到達車站，從車站上車，從車上下車出站，從車站到達座標XY，列車執行從A站到B站（相鄰兩站），列車在A站停車，在車站等待，從A車站到同城B車站，等等

舉例，某人從XY1到車站A乘車次F1到達T1站後，再到同城T2站乘車次F2到達B站，最終到XY2的路徑可能是：

Day1 5：00 XY1

Day1 5：40 A站（從座標XY到達車站）

Day1 7：00 A站（在車站等待）

Day1 7：30 F1車A站（從車站上車）

Day1 7：50 F1車A1站（列車執行）

Day1 7：55 F1車A1站（列車停站）

Day1 8：30 F1車A2站（列車執行）

Day1 8：35 F1車A2站（列車停站）

Day1 9：00 F1車T1站（列車執行）

Day1 9：00 T1站（下車出站）

Day1 9：50 T2站（從T1車站到同城T2車站）

Day1 10：50 T2站（在車站等待）

Day1 11：20 F2車T2站（從車站上車）

Day1 12：50 F2車B1站（列車執行）

Day1 12：55 F2車B1站（列車停站）

Day2 00：00 F2車B2站（列車執行）

Day2 00：15 F2車B2站（列車停站）

Day2 08：50 F2車B站（列車執行）

Day2 09：20 B站（下車出站）

Day2 10：00 XY2（從車站到XY2）

我寫過全國鐵路的程式，抓取過鐵路時刻表，甚至每個車站經緯度都弄下來了，只不過過時了很多

Sqd You2015-08-03 00:41:19

這樣應該可以_（：_」∠）_構建一個所有線路的並集組成的圖， 然後在圖上的邊/點標記上線路編號， 每條線路分別存下經過的邊/點編號

用這些資訊【隱式】構建一個圖， 每個點都連線了同一線路上的其他點。 要找換乘最少的線路就BFS； 找最短路就SPFA； 找k次換乘內最短路就A*什麼的亂搞一下唄

周星宇2015-08-04 20:19:36

不太明白問題中的所有路徑究究竟是什麼意思，顯然它不是多項式條嘛…

那就變成了如何求最優換乘路徑啦。

在每個公交站x建一個點，以及停靠在此處的所有公交線路y各建一點，記y（x）為線路y在x站所建點。

對於每一個y（x）向x連一條有向邊，權值0//下車

對於每一個x向y（x）連一條有向邊，權值為等車平均時間//等車，也可以按時間搞個分段函式什麼的

對於公交線路上相鄰的兩點y（x1）和y（x2）連一條無向邊，權值為實際路程耗費時間//坐車

對於需要獲得的兩點間最優路徑，跑個最短路就完了。

給個贊嘛～

baogege2016-10-10 16:51:37

我覺得是以站點為單元，儲存每個站點所能到的直達（不用換乘）站點和所乘公交的資訊。