Модификация алгоритма Дейкстры, чтобы найти кратчайший путь с наибольшим весом

Мне нужен кусок кода, который находит кратчайший путь между узлами с наибольшим весом. Например, самый быстрый маршрут от А до D, но с наибольшим весом:

  - B- --E
     /  \ /
    A    D
     \  / \
      C - -F

Так что сейчас самое короткое будет ABD или ACD. Как только взвешивание применено, код должен выбрать самый длинный путь из двух (нелогично, а?).

Я пытаюсь изменить алгоритм для алгоритма Дейкстры, но в конечном итоге я просто пересекаю весь граф. Кто-нибудь знает, как это сделать? Даже просто алгоритм, чтобы я мог сам его кодировать, очень помог бы.

Источник

2 ответа

Решение
  1. Запустите BFS из источника (пусть будет s) на графике, чтобы найти длину кратчайшего пути из s к цели t, будь как будет d, Также отметьте d(s,v) - расстояние от s на любой узел v,
  2. Создать подграф G'=(V',E') из G такой что: v в V'только если его расстояние от источника (s) самое большее d - d(s,v) <= d, e=(u,v) в E' только если: оба u а также v находятся в V',
  3. Создать новый график G*=(V*,E*), где V'=V*и ребро (u,v) в E* если это в E' А ТАКЖЕ d(s,u) < d(s,v),
  4. Установите новую функцию веса w*(u,v) = -w(u,v)и запустить Беллмана Форда на G* с помощью w*,
  5. Самый тяжелый кратчайший путь в G от s в t имеет вес -d(t)и найденный BF путь совпадает.

Временная сложность алгоритма O(VE)Так как Беллман-Форд является узким местом.

Доказательство правильности

Утверждение 1: кратчайший путь из s в t не содержит циклов.
Доказательство простое, удалив цикл, мы получим более короткий путь.

Утверждение 2. Все кратчайшие пути из s в t находятся в G'
Доказательство: Поскольку все кратчайшие пути из s в t имеют длину dи мы исключили только узлы с расстоянием от s длиннее чем d, мы удаляем только узлы, которые не нужны для кратчайших путей.

Утверждение 3. Все кратчайшие пути из s в t находятся в G*,
Доказательство: предположим, что мы удалили некоторые края (u,v) в кратчайшем пути, и пусть этот путь будет s->...->x->u->v->y->...->t, Обратите внимание, что путь v->y->..->t имеет длину d-d(s,u)-1 (при условии, d(s,u) минимально)
Тем не менее, обратите внимание, что от строительства E*, d(s,v) <= d(s,u) (иначе (u,v) не был бы удален). Итак, путь есть s->...->v->y->...->t с расстояния от s: d(s,v) + d-d(s,u)-1 <= d(s,u) + d - d(s,u) -1 <= d-1 - противоречие с минимальностью d,

Утверждение 4: нет циклов в G*,
Доказательство: предположим, что есть цикл в G*: v1->v2->vk->v1, По определению G'все узлы достижимы из s, Без потери общности, допустим d(s,v1) минимален для всех остальных d(s,vi) (иначе поверните индексы, чтобы соответствовать этому предположению). Но есть путь v1->v2->...->vk->v1, и d(s,v1)=d(s,v1), Это означает, по крайней мере, для одного края (vi,vi+1) на этом пути, d(vi) >= d(vi+1) - что противоречит конструкции E*и цикл не существует в G*.

Утверждение 5: алгоритм правильный.

Из правильности Беллмана-Форда, а так как G* не содержит отрицательных циклов (циклов вообще нет), BF найдет путь с минимальным весом согласно w* в G*, Этот путь имеет максимальный вес в соответствии с wот строительства w*,
так как все кратчайшие пути в G также существуют в G* (и только их), этот путь также самый короткий путь в G с максимальным весом.

QED

Источник

Вы можете использовать Dijkstra, если вы корректируете свой вес.

Если ваш оптимальный путь должен быть таким, который посещает наименьшее количество узлов, вы можете использовать высокий штраф p для обхода каждого ребра и вычитать реальный вес:

w'= p - w

Штраф должен быть выбран выше, чем максимальный вес wmax, чтобы предотвратить отрицательные значения w', для которых Dijsktra не работает. Он также должен быть достаточно высоким, чтобы действительно был выбран кратчайший путь. Хорошая оценка для p для графа n узлов может быть:

p ≈ n·wmax

(Редактировать: в моем первоначальном ответе предлагалось использовать взаимные веса w'= 1 /w каждого ребра вместо реального веса w в качестве альтернативы. Это не обязательно даст вам кратчайший путь, но тот, чей вес велик, при прохождении нескольких ребер. Это решение не работает во многих случаях. Однако оно полностью не зависит от метода штрафа, который не использует взаимные значения.)

Источник
Другие вопросы по тегам