Я пытаюсь реализовать алгоритм dijkstra с приоритетной очередью, но я не могу понять, как это работает. Я читал много руководств в Интернете, но я не могу понять этот алгоритм вообще.
Мой вопрос: каков приоритет для каждого node? Я думаю, что это вес входящего края с минимальным значением, но я не уверен. Это правда?
Второй вопрос, когда я извлекаю корень очереди, как работает, если этот node не является смежностью ни с одним из посещенных узлов?
Вы должны использовать 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:
Обзор проблем путей
Дейкстра