Найти кратчайшие пути в графе от s до всех вершин

Question

Учитывая следующую проблему:

Учитывая ориентированный граф G = (V, E) с весовой функцией W: V → R, опишите алгоритм которые находят кратчайшие пути от S до всех других вершин, где длина путь равен сумме всех вершин. Вам нужно изменить существующий алгоритм, чтобы это работало, поэтому нет необходимости писать новый алгоритм.

Обратите внимание, что весовая функция находится на вершинах, а НЕ (!!) на краях. Я думал о том, чтобы изменить алгоритм Беллмана-Форда и изменить проверку Relax на следующее:

1.if d[v]>d[u]+w[u]
 1.1 d[v] <<--  d[u]+w[u]
 1.2 PI[v] <<-- u

Я не думаю, что это работает достаточно хорошо, есть идеи, в чем может быть проблема?

спасибо, Рон

Answer 1

пусть w:V->R будет вашей весовой функцией.

Создайте функцию взвешивания: w':E->R следующим образом: w'(u,v) = w(v)

Запустите dijkstra / bellman-ford с помощью w '.пусть d '[v] будет минимальным весом пути к v, согласно w'.

Тогда, если кратчайший путь s->u1->u2->...->un->v, вы получите: d'[v] = w'(s,u1) + w'(u1,u2) + ... + w'(un,v) [по правильности dijkstra / bellman fofrd]и, таким образом, d'[v] = w(u1) + w(u2) + ... + w(un) + w(v) [по определению w '].

так что в целом вы получите: d[v] = w(s) d'[v] и d [v] - кратчайший путь для вершин.

Answer 2

Я думаю, алгоритм Флойд-Варшалла - лучшая отправная точка.Конечно, Википедия сегодня протестует:).