Как рассчитать кратчайший путь для графа со взвешенными вершинами?

Question

Я пытаюсь выяснить, как рассчитать кратчайший путь для графа со взвешенными вершинами.Классические алгоритмы, такие как Dijkstra и Floyd – Warshall, обычно работают с взвешенными ребрами, и я не вижу способа, как применить их к моему случаю (взвешенные вершины):

Один изу меня были идеи преобразовать график в более классический вид с взвешенными ребрами.Вот что я получил:

Здесь у нас есть моно- и двунаправленные взвешенные ребра, но я все еще не уверен, какой алгоритм будет обрабатывать это, чтобы найти самый короткийпуть.

Answer 1

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

Но вам не нужно беспокоиться очто-нибудь из этого ...

Алгоритм Дейкстры очень легко адаптировать к затратам на вершину без использования такого преобразования.Когда вы пересекаете ребро, вместо new_vertex_cost = old_vertex_cost + edge_weight , вы просто делаете new_vertex_cost = old_vertex_cost + new_vertex_weight .

Answer 2

Вы можете свести задачу к классической задаче кратчайшего пути и использовать Дейкстру, Беллмана-Форда или Флойд-Варшала в зависимости от цели.Для простоты в дальнейшем я предполагаю, что все веса неотрицательны.Я считаю такое предположение разумным, поскольку в вопросе упоминается использование алгоритма Дейкстры для решения проблемы.В конце концов, это предположение можно осторожно удалить.

Рассмотрим наиболее общую форму задачи: предположим, что G = <V, E> - это ориентированный взвешенный граф с весами на ребрах и вершинах.Построить график H = <V', E'> с весами только по ребрам следующим образом: Для любого узла v в G создайте два узла v_in и v_out в H;добавить ребро (v_in -> v_out) с весом, равным весу узла v в G.Кроме того, для любого ребра (u -> w) в G добавьте ребро (u_out -> w_in) в H (новое ребро имеет тот же вес, что и исходное ребро).

Чтобы подвести итог, для любой вершины в исходном графе добавьте две вершины в H, одну, предназначенную для входящих ребер, а другую, предназначенную для исходящих ребер (также, подключите новые коррелированные узлы вH на основе веса их соответствующей вершины в G).

Теперь у вас есть ориентированный взвешенный граф H без веса на вершинах, но только на ребрах.Легко доказать, что кратчайший путь между (s_in, t_out) в H совпадает с кратчайшим путем между (s,t) в исходном графе G.

Доказательство основано на том факте, что любой такой путь проходит через ребро (v_in, v_out) в H тогда и только тогда, когда соответствующий путь в G проходит через узел v.

Что касается анализа, у нас есть |V'| = 2|V| и |E'| = |E| + |V|.Таким образом, сокращение не влияет на асимптотику используемого алгоритма для поиска кратчайших путей.