Алгоритм Дейкстры с минимальной приоритетной очередью

Я пытаюсь реализовать алгоритм dijkstra с приоритетной очередью, но я не могу понять, как это работает. Я читал много руководств в Интернете, но я не могу понять этот алгоритм вообще.

Мой вопрос: каков приоритет для каждого node? Я думаю, что это вес входящего края с минимальным значением, но я не уверен. Это правда?

Второй вопрос, когда я извлекаю корень очереди, как работает, если этот node не является смежностью ни с одним из посещенных узлов?

Ответы

Ответ 1

Вы должны использовать priority queue, где vertex с самым коротким расстоянием от стартового vertex получит наивысший приоритет. Первоначально все vertices будут иметь кратчайшее расстояние бесконечности, а стартовое vertex будет иметь кратчайшее расстояние 0.

Начните с вставки всего vertices (с его edges) из графика внутри PQ. Удалите vertex из PQ и исследуйте все его edges. Сравните кратчайшие расстояния со всеми соседними vertices, и если какое-либо расстояние меньше самого короткого расстояния на текущем vertex, обновите ближайшее vertex кратчайшее расстояние внутри PQ. Продолжайте, пока PQ не пуст. vertices, который не получил edges, закончит с кратчайшим расстоянием бесконечности, потому что невозможно "добраться до них" от стартового vertex. Однако они будут удалены из PQ.

псевдокод

initialize graph
initialize pq
pq.insertAll(graph.getVertices())

while (pq is not empty) {
  vertex = pq.remove()
  edges = vertex.getEdges()

  for all edges {
    destination = edge.getDestination()
    newDistance = edge.getLength() + vertex.getDistance()
    if (newDistance < destination.getDistance()) {
      destination.setShortestDistance(newDistance)
      pq.update(destination)
    }
  }
}

Ссылки MIT OpenCourseWare:
Обзор проблем путей
Дейкстра