Multi-source single destination algorithm

Question

I have a graph where I need to find distances from multiple sources to single destination. I know how to find single source to multi destination using dijkstra's algorithm.

I found an accepted answer here: Algorithm like Bellman-Ford, only for multiple start, single destination?

But I don't understand why it will work. can anyone explain why this answer works?

Answer 1

It works because if you have an (original) source s, and your target t - in the modified graph, you reverse the edges and find a shortest path from t to all nodes, including to s.

This path is t->v1->v2->...->vk->s

Each edge (u,v) in this path exist if and only if there is an edge in the original graph (v,u), so the above path in the reversed graph can be directly translated to a path:

s->vk->vk-1->...->v2->v1->t

The weight of the paths is identical, and there is no shorter path, otherwise - you would have found it on the reversed graph.

---

As a side note, I personally prefer to transform multiple source problem to single source problem by creating a new dummy node x, and create an edge from x to any of the sources with weight 0, and then run shortest path algorithm with x as the source.
(Assuming what you need is the shortest path from some source to the target)