5
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 7, 2019 at 21:22
  • 2
    $\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. ♦
    Commented Apr 7, 2019 at 23:50

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