Все кратчайшие пути к заданной вершине

Question

Для заданного графа G = (V, E) и весовой функции w: E -> R + (только положительные веса для ребер в графе), мне нужно найти все кратчайшие пути от каждой вершины v в V до заданной вершины k.

Я подумал о том, чтобы реверсировать ребра в графе, а затем запустить Dijkstra's algorithm из вершины k. Интересно, является ли кратчайший путь p от k до v1 на самом деле кратчайшим путем от v1 до k в исходном графе (перед реверсированием ребер).

Буду благодарен, если кто-нибудь сможет объяснить, если и почему это происходит/не происходит.

Заранее спасибо.

Answer 1

(Это не будет самым формальным доказательством в мире, но, надеюсь, его достаточно хорошо, чтобы убедить себя).

Допустим, для вершины v , в графе G, кратчайший путь от об к K имеет длину м. Две вещи, которые вы хотите знать, являются:
1. В обращенном графе G * существует путь длины м от K к об.
2. В обратном графике, G *, нет пути от K к об, которые короче, чем м.

Перед тем, как начать, мы можем взять одну вещь на веру:
Лемма 1: Если у вас есть ориентированный путь из вершины об к вершине ж, и вы реверс каждое ребро на пути, то у вас есть путь от вершины w до вершины v. Это доказуемо, но я думаю, что это довольно здравый смысл. Я докажу это, если вы захотите.

Для точки 1: Рассмотрим путь в G от об к K состоящий из м края. Если вы реверс каждой из этих краев, вы будете иметь путь от K к против длиной м (по лемме 1).

Для точки 2: Предположим, что существует путь в обратном графа G *, от K к об длины п < м. Если обратный этот путь, то есть путь длины п от против в к (Лемма 1).Это означает, что существует путь от об к K в исходном графе, который короче, чем м, что противоречит утверждению о том, что путь длиной м является самым коротким.