3
$\begingroup$

In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at the beginning of the algorithm.

However, I'm wondering if we can use the same technique to solve Multiple Source Shortest Paths in a weighted graph using Dijkstra's algorithm (for non-negative weight edges) and Bellman-Ford algorithm (when negative weight edges are allowed, and of course there is no queue here).

If I'm right, we can think in this situation as there are edges with weight equal to zero between any source and all other sources in the graph.

So, can we use this technique in a weighted graph? And why?

$\endgroup$
3
$\begingroup$

Yes. Here is the trick that always works: create a new source, $s_0$, and add an edge (with length 0) from $s_0$ to each of your starting vertices. Then, run any shortest-paths algorithm starting from $s_0$ to compute the distance from $s_0$ to each other vertex.

Your technique for BFS is equivalent to this; but this is more general and can be used with Dijkstra's algorithm, Bellman-Ford, or any other shortest paths algorithm.

$\endgroup$
  • $\begingroup$ Thank you, but when we store the graph, do we need to construct these edges? I mean, is it wrong to set $distance_i = 0$ for all these source vertices? $\endgroup$ – Abdulkader Apr 7 at 21:22
  • 1
    $\begingroup$ @Abdulkader, that's up to you. You can construct them explicitly; or just consider how the algorithm would work if they were present, and adjust the code of your algorithm accordingly, without explicitly adding them. As long as it always yields the same result, it doesn't matter. $\endgroup$ – D.W. Apr 7 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.