Imshow в полярных координатах

Рассмотрим график, показанный ниже, с источником как Vertex A. Сначала попробуйте запустить сам алгоритм Дейкстры.

[/g16]

Когда я говорю о Dijkstra's алгоритм в моем объяснении, я расскажу об алгоритме Дейкстры, как это реализовано ниже,

[/g17]

Итак, начиная значения ( расстояние от источник к вершине ), первоначально назначенный каждой вершине, являются

. Сначала мы извлекаем вершину из Q = [A, B, C], который имеет наименьшее значение, то есть A, после чего Q = [B, C]. Примечание. A имеет направленное ребро для B и C, оба из них находятся в Q, поэтому мы обновляем оба этих значения,

Теперь мы экстракт C как (2 & lt; 5), теперь Q = [B]. Обратите внимание, что C ни к чему не связан, поэтому цикл line16 не запускается.

Наконец, мы извлекаем B, после чего . Примечание B имеет направленный край к C, но C отсутствует в Q, поэтому мы снова не вводим цикл for в line16,

Итак, мы закончили с расстояниями как

Обратите внимание, как это неправильно, поскольку кратчайшее расстояние от A до C равно 5 + -10 = -5, когда вы идете .

Итак, для этого графика алгоритм Дейкстры ошибочно вычисляет расстояние от A до C.

Это происходит потому, что Алгоритм Дейкстры не попробуйте найти более короткий путь к вершинам, которые уже извлечены из Q .

То, что делает цикл line16, - это взять вершину u и сказать «эй выглядит как мы можем перейти к v из источника через u, является ли это (alt или альтернативное) расстоянием лучше, чем текущий dist [v], который мы получили? Если это так, обновите dist [v] "

Обратите внимание, что в line16 они проверяют все соседи v (т. Е. Направленное ребро существует от u до v), из u, которые все еще находятся в Q. В line14 они удаляют посещенные заметки из Q. Так что, если x является посещенным соседом u, th e path даже не рассматривается как возможный более короткий путь от источника к v.

Это действительно полезно , если все весовые коэффициенты положительные числа , потому что тогда мы не будем тратить свое время на рассмотрение путей, которые не могут быть короче.

Итак, я говорю, что при запуске этого алгоритма, если x извлекается из Q до y, тогда его невозможно найти путь - , который короче. Позвольте мне объяснить это с помощью примера

. Когда y только что был извлечен, и x был извлечен перед собой, тогда dist [y]> dist [x], поскольку в противном случае y было бы извлечено до x. (line 13 min distance first)

И как мы уже предположили , что веса ребер положительны, т. е. длина (x, y)> 0. Поэтому альтернативное расстояние (alt) через y всегда должно быть больше, то есть dist [y] + length (x, y)> dist [x]. Таким образом, значение dist [x] не было бы обновлено, даже если y рассматривался как путь к x, поэтому мы заключаем, что имеет смысл рассматривать только соседи y, которые все еще находятся в Q (примечание к примечанию в line16),

Но это зависит от нашего предположения о положительной длине ребра, если длина (u, v) & lt 0, то в зависимости от того, насколько отрицательно это ребро, мы могли бы заменить dist [x] после сравнения в line18.

Таким образом, любой расчет dist [x], который мы делаем, будет некорректным, если x удаляется до того, как все вершины v - такие, что x является соседним v с отрицательным ребрами, соединяющим их - удаляется.

blockquote>

Поскольку каждая из этих v вершин является второй последней вершиной на потенциальном «лучшем» пути от источника к x, который отбрасывается алгоритмом Дейкстры.

Итак, в примере Я сказал выше, ошибка заключалась в том, что C был удален до того, как B был удален. В то время как C был соседом B с отрицательным ребром!

Чтобы уточнить, B и C являются соседями А. B имеет один соседний C и C не имеет соседей. length (a, b) - длина ребра между вершинами a и b.