單向的最短距離路線(筆記)

昨天去聽一門北一女中的選修課，是成大數學系許瑞麟教授授課，他給的題目是由下圖的結點①到結點⑨，所經過的最短距離路徑(或花最短時間的路線)，每條路線上的數字當作長度(或所花的時間)。

許教授有講解一個解題的algorithm，我邊聽邊想，找到一個解決這個問題的方法：

對於每一個結點 j，我記錄所有從結點1到達結點 j 的路線長度，取其最小值。取最小值的動作是在每一個結點都要做。

所以我這樣做：先把結點i會到達結點 j 的路徑長度記為a_ij，寫成一個上半矩陣。

第一步：先寫出相連兩結點的路徑長，如下：

	①	②	③	④	⑤	⑥	⑦	⑧	⑨
①		1	2
②				6	12
③				3		4
④					4	3	15	7
⑤							7
⑥								7	15
⑦									3
⑧									10
⑨

第二步：記錄所有的a_1j，取最小值，記法如下：

 所以，最短路徑可記為：

即①→③→④→⑤→⑦→⑨為最短的路線，距離和為19單位。

不過，如果路線改成雙向的，似乎無法用這個方法來處理，或是需要再修正，我還要再想一想。