先前介紹的BFS可以幫我們找到最短路徑，但是那是在將各個edge都視為等長的情況下，假若要多考慮edge的長度，那BFS就不夠用了。這章節我們將介紹能夠考慮edge權重的最短路徑演算法。

首先來介紹一個名詞，SPT(shortest path tree)：

在上圖Graph範例中我們發現，點0到其他各點的最短路徑答案，會形成一個Tree，我們稱這個Tree為SPT。

接著以下圖為範例推導出找到Graph中的SPT。可以看到粗體箭頭就是當A為起點，到其他個點的最短路徑，而節點上洋紅色的數字代表起點到達該點的距離：

第一個嘗試，我們很單純的使用dfs看看：

會發現最終答案不太對，如果我們對於已經加進SPT的節點都沒有任何作為很明顯行不通，這樣有非常大的機率會錯過最佳解。那如果我們在dfs時不要直接跳過已加進SPT的節點，而是判斷會不會有更好的洋紅數字呢？

這就是以下的第二個嘗試：

每次dfs在拜訪鄰居時，也一併判斷是否有更短距離，如果能讓鄰居擁有更小的洋紅數字的話，就取代原先的答案。這個行為稱為relax an edge，或稱relaxation。

但很遺憾，這樣做還是沒有達到最佳解答。為什麼呢？關鍵在於dfs過的點我們就不會再重新拜訪，也代表如果我們dfs的順序錯了，那就會錯過最佳解的路徑。

在當我們第二個dfs選擇先拜訪B點時，就註定失敗了，因為最佳路徑會是A → C → B → D，但是因為我們先拜訪了B，就錯過了B → D這條路徑，讓SPT變成了A → C→ D。

所以只要我們選擇對的點進行dfs，就可以獲得最佳解了，而選擇的依據也很簡單，就是先選擇洋紅數字較小的點來進行dfs即可：

以上第三種解法稱為Dijkstra’s Algorithm。

Dijkstra可以有效率地幫我們找出起點到所有其他節點的最短路徑，但我們平常最常用的功能是想找到某個特定終點的最短路徑，若是這樣的話有沒有方法可以再優化呢？

聰明的人類這時就想到，既然Dijkstra是利用每個節點當前的洋紅數字判斷，那只要在這個環節去影響演算法，就可以增快找到終點的速度了～

該如何影響呢？就是在判斷洋紅數字之餘，再多加上一個heuristic h(v, goal)的值：

如上圖，我們針對所有的點距離終點點6先給出一個猜測值，而在判斷下一個dfs該輪到誰時，就不只是判斷neighbor身上的洋紅數字，而是洋紅數字 + h(v, goal)，這樣就可以少dfs不必要的節點，更快找到走到終點的最短路徑。

以下是單純Dijkstra的節點選擇，當點0做完relaxation後，因為點2的距離較近，會先選擇到點2做dfs：

↓

而A*就會因為heuristic的關係，點2是1 + 15 = 16；點1是2 + 3 = 5，所以會跳過點2，改往點1前進：

只不過看似很有效率的做法，有個不太可控的因素，那就是heuristic的值該如何決定？答案就是沒有一定的標準，就是只能靠經驗法則了～

這邊老師提供了一個很酷的程式讓我們可以視覺化不同演算法在找到達終點最短路徑的過程：

http://qiao.github.io/PathFinding.js/visual/

下面是擷取Dijkstra和A*的結果比較：

Dijkstra：

A*：

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License