кратчайшего алгоритм пути Дейкстры

Question

алгоритм Дейкстров в КСПСЕ p.595 имеет следующий код в строке 7:.

for each vertex v \in Adj[u] 

Эта линия выбирает для перебора всех соседей узла v Узел V здесь является один алгоритм в настоящее время обрабатывает и добавляет в кратчайшее дерево путей. Однако среди тех соседей по v, которые уже находятся в наборе S, обрабатываются на &, а те узлы в S образуют кратчайшее дерево путей. Ни один из узлов в наборе S не может иметь путь-thru- v, что меньше пути, уже указанного в T. В противном случае этот путь был пройден до тех пор.

Таким образом, не следует эта строка 7 будет лучше, так как

for each vertex v \in Adj[u] \intersect Q // Q = V \ S 

или, в равной степени,

for each vertex v \in Adj[u]\S 

?

// ===========================

ДОБАВЛЕНИЕ объяснения:

когда вы обрабатываются (обработано = установите расстояние и родительский вектор записей всех его ближайших соседей) узел u и добавьте его в дерево, , что узел u находится на кратчайшем расстоянии от источника. если бы существовал недревесный узел z, так что более короткий путь к u существовал бы через него между источником & u, этот узел z был бы обработан до u.

// ======================

ДОПОЛНЕНИЕ 2: длинный комментарий к полезному ответу Хавьера ниже:

Поместите все ребра в графе в массиве говорят «EDGES» - одно ребро, одна запись массива. , каждая запись массива содержит ребро (u, v), вес по краю и 2 указателя - от одного до узла u и от одного до узла v.

график представлен как список смежности.

Adj [u] по-прежнему является связанным списком, однако этот связанный список находится в структуре массива. Значения узлов в этом списке, на этот раз, представляют собой индекс EDGES, соответствующий этому ребру.

Так, например, Узел u имеет 2 связных инцидента с ним: (u, x) & (u, y). Edge (u, x) сидит в 23-й ячейке EDGES и (u, y) на 5-й. Затем Adj [u] является связанным списком длины 2, узлы в этом списке равны 23 и 5. Скажем, Adj [u] [0] .edgesIndex = 23 и Adj [u] [1] .edgesIndex = 5 , Здесь Adj [x] [i] .edgesIndex = 23 для некоторого i в связанном списке в Adj [x]. (Adj [j] [i], являясь узлом в связанном списке, дополнительно содержит поля «next» и «prev».)

И, EDGES [23] имеет одну ссылку на соответствующую запись (u, x) на Adj [u], а другая - на Adj [x]. Я оставляю строку 7 как есть, но на этот раз, после того как я обработаю ребро (u, v) в этом цикле (я узнал об этом ребро из Adj [u]), я удаляю это ребро из связанного списка Adj [u], оттуда я перехожу к соответствующей записи EDGES, которая имеет ссылку на соответствующую запись Adj [x] [i]. я удаляю их все - EDGES [23], Adj [u] [0] и Adj [x] [i] (независимо от того, что там есть.) Со всеми структурами массивов я могу обрабатывать все это в постоянное время для каждого ребра.

По-прежнему представление списка смежности может отслеживать местоположение (v, u) из (u, v) и удалять их в постоянное время и теперь обрабатывать только по краям в этом пересечении, которое я ищу асимптотически такой же объем используемой памяти и с большей эффективностью времени.

// ====================

ДОПОЛНЕНИЕ 3:

исправляющие одну вещь в КРОМЕ 2 выше:

, что я написал, что добавление может занять больше - не меньше времени, чем алгоритм без него:

удаляет ссылки в связанных списках в Adj [u] и Adj [x] и соответствующую запись EDGES , прямую -memory look-ups во время всего этого маловероятно чтобы уменьшить количество циклов процессора, чем уменьшение ребер в алгоритме как есть.

Он по-прежнему проверяет каждое ребро (u, v) ровно один раз, а не дважды - один раз для (u, v) и один раз для (v, u), и ясно в том же асимптотическом времени, что и алгоритм без него , Но для небольшого выигрыша в абсолютном времени обработки и с большей стоимостью используемой памяти.

Другой альтернативой является: добавление линии что-то вроде

if (v \in S) then continue; 

как первый из для цикла. это может быть реализовано путем сохранения S как массива из булева языка S [| V |] и установки его значений соответственно, так как каждая вершина равна , добавленной к множеству S, что в основном является тем, что javier говорит в своих ансах.

Answer 1

Пересечение Adj[u] с Q является правильным, однако это не очень хорошая идея, потому что в конце вам нужно будет перебирать все элементы Adj[i]. Я не думаю, что есть способ обход этого.

Это будет работать только в том случае, если вы сможете найти способ пересечения этих двух наборов ОЧЕНЬ эффективно, то есть ничего лучше, чем O (n).

Существует хорошее усовершенствование, которое вы реализуете, чтобы отметить все узлы, которые были установлены, а затем, если узел v разрешен, вы можете игнорировать остальную часть внутреннего цикла.