迪卡斯特拉演算法

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢
迪卡斯特拉演算法嘅示範

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

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。

睇埋[編輯]

[編輯]

  1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601.
  2. Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5.