Frank's 資訊科技潮流站

隨著科技的發達，大家的車上漸漸多了一個東西

叫作「GPS衛星導航」

這東西不只可以讓你看所在地圖...還可以規劃路線，叫電腦找一條最近的路！

這挺神奇的，而且用到了數學的概念

讓我們來看看吧...

其實看似簡單的一張地圖，每一條路都已經記載了相關的資訊

像是 行走必須的時間 (如果該路段有塞車時間還會增加)

就像這張圖一樣

例如這張圖，上面的數字代表通過所需的時間

那麼，要怎麼走，才能最快到達目的地呢？

當然，我們可以使用「目測法」

但是，「目測法」並不科學，而且面對比較大的地圖，就傷腦筋了

因此，要了解一下，我們沒有眼睛的電腦...是怎麼找路的

首先我們從起點開始走！

起點一開始，有三條路可以選！

距離分別是 1 、 4 、 3

我們選擇走 1 那條，並且把走過的地方標起來~~

再來，我們還是有三條路可以走

不過這次距離分別是 9 、 4 、 3

因為 3 最短，所以就走了 3 ，並且標記起來...

走了 「3」 這條路，猛然發現接下來有岔路

所以，我們接下來的道路選擇，變成有 4 條

這四條分別是 9 、 4  、 1 、 2

我們選擇 1 走，並且標記起來

那個路徑累積的距離是 4

同理，我們有三條路可以走...

分別是 9(綠) 、 2(粉紅) 、 2(紫色)

雖然有兩條路都是 2 的距離

但是他們的起始時間分別是 3 、 4

所以，我們選起始時間是 3 的優先來走

這個時候，不知不覺就到達終點了

所以這張圖的最短距離是...5

教學完畢，謝謝大家 (?)

---

至於這程式要怎麼寫啊？

據說要用遞迴寫，

老實說我...還不會....

總之這邊先把「數學」搞懂！