Трассировка реализации алгоритма Дейкстры в python
Я пытаюсь отследить реализацию алгоритма Дейкстры на python с использованием очереди приоритетов, но я не мог следовать, потому что я новичок в python.
вот реализация
def dijkstra(edges, f, t):
g = defaultdict(set)
for l,r,c in edges:
g[l].add((c,r))
g[r].add((c, l))
q, seen, = [(0,f,())], set(),
while q:
(weight, v1, path) = heappop(q)
if v1 not in seen:
seen.add(v1)
path += (v1,)
if v1 == t:
return weight, path
for k, v2 in g.get(v1, ()):
if v2 not in seen:
heappush(q, (weight+ k, v2, path))
return float("inf")
- во-первых, почему он использовал
g = defaultdict(set)вместоg = defaultdict(list)и использовал .add() вместо .append() - Я понимаю, что в начале алгоритма Дейкстры вам нужно установить все веса для всех узлов на бесконечность, но я не вижу этого здесь.
- также в каких строках узел определяет путь, по которому он проходит, например, в какой строке принимается решение идти влево или вправо. простым словом, где в коде делается взвешенная линия между узлами.
комментарий, объясняющий, что произошло в каждой строке кода, был бы очень полезен для меня, чтобы понять его.
Ответы 1
Что касается ваших вопросов:
во-первых, почему он использовал
g = defaultdict(set)вместоg = defaultdict(list)и использовал.add()вместо.append()
Это будет работать так же хорошо с list. Конечно, метод, который будет использоваться (add или append), следует из этого выбора. Единственное преимущество, которое я вижу, это то, что с set вы не будете добавлять одно и то же ребро дважды. В общем, граф может иметь несколько ребер между одними и теми же двумя вершинами, и они могут даже иметь одинаковый вес: когда это происходит, нет причин рассматривать эти повторяющиеся ребра по отдельности, и set гарантирует, что повторяющиеся ребра будут проигнорированы.
Я понимаю, что в начале алгоритма Дейкстры вам нужно установить все веса для всех узлов на бесконечность, но я не вижу этого здесь.
Существуют различные способы реализации алгоритма. Действительно, вы можете добавить все вершины в приоритетную очередь в самом начале, где все они, кроме исходной вершины, начинаются с бесконечным весом. Но немного эффективнее просто исключить эти «бесконечные» вершины из очереди: таким образом размер очереди будет меньше, и первые добавленные в очередь вершины будут добавлены немного быстрее. Таким образом, любая вершина, не находящаяся в очереди, на самом деле является вершиной с бесконечным весом.
также в каких строках узел определяет путь, по которому он проходит, например, в какой строке принимается решение идти влево или вправо. простым словом, где в коде делается взвешенная линия между узлами.
В коде решения не видно. Все пути являются потенциальными победителями, пока не будет найден целевой узел. Прежде чем это произойдет, все частичные пути, которые были построены, находятся в куче, и именно характеристика кучи определяет, какой путь будет следующим, который будет расширен до соседних узлов. И тогда эти более длинные пути (с большим количеством вершин) снова будут брошены в кучу, где магия кучи снова сделает свое дело. Итак, если вы ищете «решение», внутри кучи будет принято только решение: оно говорит нам, какой путь с наименьшим весом присутствует в куче. Таким образом, основной цикл может работать немного по одному пути (для его расширения), но затем в следующей итерации он может работать по совершенно другому пути. И так продолжается до тех пор, пока вдруг не обнаружит, что достигла целевой вершины. Только в этот момент все остальные пути, которые все еще были кандидатами в куче, игнорируются.
Если вы хотите узнать немного больше об этой скрытой магии heappop и heappush, прочитайте статью Википедии на эту тему.
Не оптимально
Хотя алгоритм правильный, он не является эффективной реализацией. Следующий оператор указывает на путь, который нужно скопировать, и этот путь может иметь до n элементов, поэтому он имеет временную сложность в наихудшем случае O(n) при одном выполнении, что дает алгоритму временную сложность в наихудшем случае O( n²лог):
path += (v1,)
Чтобы избежать этого, обычно не отслеживают пути в целом, а сохраняют только обратную ссылку на предыдущий узел, из которого мы пришли. Затем, когда придет время, когда мы попадем в целевой узел, мы сможем вернуться, следуя этим обратным ссылкам, и построить путь только один раз. Поскольку сохранение обратной ссылки занимает постоянное время, это улучшение сделает алгоритм временной сложностью O(nlogn).
Стоимость приоритетной очереди, здесь куча, обычно затмевает все остальные затраты, но здесь копирование пути может сильно увеличить значение K, возможно, в N раз больше стоимости. Таким образом, стоимость может быть O (N ^ 2 lg N).
@Серт, абсолютно. ОП не спрашивал о временной сложности, но я добавил раздел об этом.
Это откуда взялся код? theamdara.blogspot.com/2018/02/dijkstra-in-python.html — тот сайт вроде принимает вопросы, почему бы не задать там?