Почему алгоритм Дейкстры расслабляет смежные ребра с вершинами уже в дереве кратчайшего пути?

Почему в псевдокоде DIJKSTRA в главе 24 стр. 658 CLRS Third Edition во внутреннем цикле при ослаблении смежных ребер из новой добавленной вершины разрешено ослабление ребер, уже извлеченных из очереди и добавленных в кратчайший путь к дереву?

while(Q not empty){
 u = extractMin from Q;
 Add S to the shortest path tree;
 for each vertex v adjacent to u 
 relax(u,v,w)

}

Почему внутренний цикл не проверяет, является ли вершина уже частью дерева кратчайшего пути, например,

while(Q not empty){
     u = extractMin from Q;
     Add S to the shortest path tree;
     for each vertex v adjacent to u 
     if v is in Q 
      then relax(u,v,w)

    }

Какой правильный подход?


algorithm clrs
person Sohail Khan    schedule 04.02.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Первое, что делает relax, это проверяет

if v.d > u.d + w(u,v)

Если v уже находится в дереве кратчайшего пути, проверка всегда будет завершаться ошибкой, и relax не будет продолжено. Проверка if v is in Q была бы излишней.

Однако, если if v is in Q является значительно более быстрой операцией, чем if v.d > u.d + w(u,v) в конкретной реализации алгоритма, в том числе это может оказаться полезной оптимизацией.

person Janne Karila    schedule 04.02.2015

arrow_upward
2
arrow_downward

Оба подхода функционально правильны. Однако ваша версия менее оптимальна, чем версия CLRS. Вы не хотите делать if v is in Q, потому что это операция O (log n), тогда как if v.d > u.d + w(u, v) - это O (1). В начале алгоритма Q содержит все вершины графа. Так что, скажем, для очень большого редкосвязного графа ваша версия окажется намного хуже, чем CLRS.

Ваш вопрос, однако, не совсем безоснователен. Объяснение алгоритма Дейкстры в CLRS немного сбивает с толку, что собственно и привело меня в эту ветку обсуждения. Глядя на псевдокод на странице 658:

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S = 0
3 Q = G.V
4 while Q not empty
5     u = EXTRACT-MIN(Q)
6     add u to S
7     for each vertex v in G.Adj[u]
8         RELAX(u, v, w)

спрашивается, какой смысл вообще поддерживать S? Если мы полностью избавимся от него, удалив строки 2 и 6, алгоритм все еще будет работать, и после его завершения вы сможете напечатать кратчайший путь, следуя указателям-предшественникам (уже сохраненным в каждой вершине) в обратном направлении по графу (используя PRINT-PATH(G, s, v) на стр. 601, как описано на странице 647). S, кажется, используется здесь больше как инструмент объяснения, чтобы проиллюстрировать тот факт, что Дейкстра является жадным алгоритмом, но в реальной реализации графа, мне кажется, это не понадобится.

person Andrei Tudorancea    schedule 25.10.2016