迪卡斯特拉演算法

迪卡斯特拉演算法嘅示範

迪卡斯特拉演算法（英文：Dijkstra's algorithm）係由荷蘭電腦科學家艾斯加·迪卡斯特拉（Edsger W. Dijkstra）諗出嚟嘅一個搵路演算法。呢個演算法會攞三樣嘢做輸入：一個圖、一個起點節點同一個終點節點；目的係俾出「成本最低嗰條路線」嚟做輸出，而如果有多過一條「成本最低路線」嘅話，是但俾其中一條做輸出。虛擬碼如下：

def pathfindDijkstra(graph, start, end): // 個演算法有三個 input，個圖（graph）、起點（start）同終點（end）
  struct NodeRecord: // 個演算法需要三件資訊：
    node // 節點
    connection // 連結
    costSoFar // 「目前嘅成本」

  // 初始化
  startRecord = new NodeRecord()
  startRecord.node = start
  startRecord.connection = None
  startRecord.costSoFar = 0
  open = PathfindingList() // 「開放表」（open list）
  open += startRecord // 將起點加入開放表。
  closed = PathfindingList() // 「封閉表」（closed list）

  // while 開放表入面仲有嘢，做...
  while length(open) > 0:
    current = open.smallestElement() // 攞開放表入面最細嗰件做現時點。
    if current.node == goal: break // 如果現時點係終點，break。
    // 如果冇 break 到，個程式會繼續行落去...
    connections = graph.getConnections(current) // 將同現時點有連結嘅節點冚唪唥搵嗮出嚟。

    for connection in connections: // 同搵到嘅連結每個做以下嘅嘢...
      endNode = connection.getToNode() // 設嗰條連結去嘅點做終點。
      endNodeCost = current.costSoFar + connection.getCost() // 計個成本。
      if closed.contains(endNode): continue // 如果嗰點係冇路走嘅，skip 去計下一條連結。
      else if open.contains(endNode):
        endNodeRecord = open.find(endNode)
        if endNodeRecord.cost <= endNodeCost: continue // 如果呢個點嘅成本並唔細過已知嘅點嘅話，skip 去計下一條連結。
      else:
        endNodeRecord = new NodeRecord() // else，將呢個點加入紀錄嗰度。
        endNodeRecord.node = endNode
      // Update 成本同連結
      endNodeRecord.cost = endNodeCost
      endNodeRecord.connection = connection
      // 再將呢點加入開放表嗰度。
      if not open.contains(endNode):
        open += endNodeRecord
      // 將現時點移出開放表，並且加佢入封閉表。

    open -= current
    closed += current

  // 做完個 while 之後...
  if current.node != goal: // 如果冇去到終點嘅話，表示搵路失敗。
    return None
  else: // 否則，compile 一個列嗮搵到嗰條路涉及嘅連結嘅表，表示條路線。
    path = [] 
    while current.node != start: 
      path += current.connection
      current = current.connection.getFromNode()
    return reverse(path) // 將條路線俾出嚟做 output。

睇埋

• 搵路
• A* 搜尋演算法