# Multiple Source Shortest Paths in a weighted graph

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?

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.
• 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? Apr 7, 2019 at 21:22