最短路徑演算法的一點經驗

最近有老師開始對GIS感興趣，於是做了一些圖層的套疊，這沒什麼，幾年前就玩過了，但這次還有更進階的，要開始把裡面的交通訊息，例如電車路線等也「資料化」，初步看起來在地圖上畫線，但有了線就要能走，能走就有怎麼走最短的問題，於是開始了這幾天的奮戰。

一開始當然是想既然都用google map了，看看有沒有提供自己設定路徑的導航，很可惜沒有，至少到目前都還沒找到，那只好硬著頭皮上了。剛開始學程式的時候有學到「走迷宮」的寫法，就是「遞迴」，可是那時候的迷宮是一個很平面，像是棋盤那樣一格一格的概念，現在換成電車路線，又有一堆交錯點和繞圈圈的路線，好像不太能等同。

既然沒頭緒，那就想到什麼寫什麼。走的是路線，就把每條電車線路線做成一個陣列，每個index放一個「車站名」，因為站名是唯一值，所以交錯時站名重複就好了，也可以用重複的站名去確認有沒有交錯。

於是用陣列方式，只要index大於零，就先往零的方向走，走到零再往回走，走到沒路再找是不是交錯點，現在看起來整個就是文組思維，雖然有時候還是走得到，但只要遠一點，或者要轉兩三個交錯點的情形，基本上就不知道走去哪裡了，而且大部分情況都不是最近的路。

http://www.csie.ntnu.edu.tw/~u91029/Path.html
找資料時看到了「最短路徑演算法」的說明，然而不管是說明還是程式範例，感覺都是有字天書，但最少從裡面看到了一個概念，就是把「路徑」的抽象化，把路線都切成「起站+一段路+終站」。於是程式砍掉重練，把路線資料改成一個陣列，每個index裡面存包含起站名、終站名和路線長度的「路線物件」。

找的時候就先從陣列裡找到起點，然後再從陣列裡頭，找有沒有起站一樣的路線，檢查終站是不是終點，不是的話再把終站當起站，然後再找一次。終而復始，總可以走到終點，然後把走過的點都記錄下來。這種走法會留下很多「走錯的路」，雖然可以藉由重複的點，把中間走錯的路刪掉，但遇到岔路多的還是很難解決。

想不懂只好再回頭啃那個演算法，這次看出「地圖」的概念，用一個二維陣列來表示地圖，並且把沒走過的路預設成false，走過的改成true，然後最重要的是走到底開始遞迴時，要把走過的路改回false。

抓到這個點後，再用剛剛窮舉的方式處理，問題就簡單多了，最後分析不是走過哪些「點」，而是走過哪些「路線」，走不到終點的就像對不起來的拼圖，試過以後就丟到一邊去，之後再分析這些「路線」的長度，來決定出「最短路徑」，問題總算解決了。

經過這次的問題，我才發現這幾年寫的程式說穿了都是「外家功夫」，範例改一改，函式套一套，邏輯判斷多跑幾次等等，雖然也能解決問題，但就像偷學少林武術的火工頭陀，即使學到大力金剛指，內功還是一點也沒有。「演算法」是程式的「內功」，但真的很難啃，因為講的是很抽象的想法，像這種走迷宮的問題，怎麼會用拼圖般的方式來解決呢？只是妙也就妙在這裡，還真的可以處理！或許有的時候，既有的經驗反而成了侷限自己牢籠吧。