Dijkstra算法

Dijkstra算法（Dijkstra's Algorithm）

Dijkstra算法是計算圖中最短路徑的算法之一，由荷蘭計算機科學家艾茲赫爾·戴克斯特拉（Edsger W. Dijkstra）在1956年提出，並於1959年發表。這個算法可以找到一個節點到圖中其他所有節點的最短路徑，特別適用於不包含負權邊的有向圖和無向圖。

定義

Dijkstra算法的目的是從圖中的單個源點出發，計算到達所有其他節點的最短路徑。其基本思想是創建一個集合，該集合跟蹤已知的最短路徑長度的節點。

算法描述

算法的步驟如下： 1. 將所有節點的最短路徑估計值初始化為無窮大，將源點的最短路徑估計值設為0。 2. 將所有節點放入未處理的集合中。 3. 當未處理的集合非空時，重複以下步驟：

  a. 从未处理集合中选择一个最短路径估计值最小的节点u。
  b. 将节点u标记为已处理，表示u的最短路径估计值是最终的。
  c. 放松节点u的所有未处理的邻接点v。即，对于每个邻接点v，如果通过u到v的路径比当前已知的最短路径估计值短，就更新v的最短路径估计值。

數學表示

設$G=(V,E)$是一個帶權圖，其中$V$是節點集合，$E$是邊集合。對於每條邊$(u,v)\in E$，其權重由函數$w:E\rightarrow \mathbb {R}$給出。Dijkstra算法可以用以下偽代碼表示：

‎

function Dijkstra(Graph, source):
    dist[source] ← 0                           // 初始化源点到自身的距离为0
    for each vertex v in Graph:                
        if v ≠ source
            dist[v] ← infinity                 // 将其他所有节点的距离初始化为无穷大
            prev[v] ← undefined                // 节点的前驱节点初始化为未定义
        end if
    end for
    Q ← the set of all nodes in Graph          // 创建一个包含图中所有节点的集合Q

    while Q is not empty:                      // 当集合Q非空时
        u ← node in Q with min dist[u]         // 从Q中取出距离最小的节点u
        remove u from Q                        // 从Q中移除节点u

        for each neighbor v of u:              // 检查u的所有邻居v
            alt ← dist[u] + length(u, v)       // 计算通过u到v的距离
            if alt < dist[v]:                  // 如果新计算的距离更短
                dist[v] ← alt                  // 更新v的距离
                prev[v] ← u                    // 将v的前驱节点设置为u
            end if
        end for
    end while
    return dist[], prev[]
end function
‎

應用

Dijkstra算法在多種場景中都有應用，包括計算機網絡中的路由選擇、地圖軟件中的導航系統、社交網絡中查找人際關係的最短路徑等。這個算法的效率和準確性使它成為實際應用中計算最短路徑的首選算法之一。

注意事項

Dijkstra算法不能處理圖中存在負權邊的情況，因為這可能會導致算法無法找到真正的最短路徑。在包含負權邊的圖中，通常使用Bellman-Ford算法來計算最短路徑。