貪心演算法單源最短路徑

『壹』 直觀理解：單源點最短路徑——Dijkstra演算法

  Dijkstra演算法是由荷蘭計算機科學家 Edsger Wybe Dijkstra於1959年提出的單源點最短路徑演算法（SSSP:Single Souce Shortest Path）。是一個解決加權圖（不含負權重的邊）中從一個頂點到其餘各個頂點最短路徑問題的演算法。Dijkstra演算法是一個集 貪心演算法 ， 廣度優先搜索（BFS） 和 動態規劃 於一身的最短路徑演算法。Dijkstra演算法的主要特點是從起源點開始，採用貪心演算法的策略，每次遍歷到始點距離最近且未訪問過的頂點的鄰接頂點，直到擴展到終點為止。
  Dijkstra演算法通過維護兩個集合： (已求出最短路徑的頂點)和 （未求出最短路徑的頂點），每次迭代地從 中移除路徑距離最小的點到集合 中，並通過這個新移入的點來更新 中各個頂點到源點的最短路徑，直到集合 為空。下面我們通過一個例子來簡單描述Dijkstra演算法的過程。
  假設我們有如下的圖，其中頂點A未此次演算法的起點：

  首先我們需要初始化兩個集合 和 ，以及 中每個頂點到源點的距離，若不直接於A相鄰，結果置為正無窮∞。

   Step 1： 從集合 中挑選出距離最小的點，這里會挑選出頂點F，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 2:： 從集合 中挑選出距離最小的點，這里會挑選出頂點E，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 3： 從集合 中挑選出距離最小的點，這里會挑選出頂點C，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 4： 從集合 中挑選出距離最小的點，這里會挑選出頂點D，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 5： 從集合 中挑選出距離最小的點，這里會挑選出頂點B，集合 和 變更為： ， ，根據最新的 ，重新計算 中頂點到源點A的最短距離。

   Step 6： 從集合 中挑選出距離最小的點，這里會挑選出頂點G，集合 和 變更為： ， ，由於集合 為空，演算法停止迭代，輸出結果。

  以上就是對Dijkstra演算法的計算過程的簡單描述。