# Shortest paths graph

Given a directed graph $G$, edge weights for each edge, source vertex $s$ and $d[v]$ for each vertex in the graph (the distance from $s$ to $v$), I need to find an algorithm that builds the shortest paths graph.

I was thinking of going on edges by BFS, but then how can I know which edge should be in the tree and how to check that the $d[v]$ for each vertex is true?

• What is a "shortest paths graph"? – Juho Dec 23 '12 at 22:51
• @Juho He probably means a tree which is a sub-graph of $G$, where any edge $(u, v)$ is present only if it is on the shortest path from $s$ to $v$. Informally, he probably wants the collection of shortest paths (1 path per vertex) in the form of a tree. But you are right, the OP needs to clarify. – Paresh Dec 23 '12 at 23:30

Thre are multiple algorithms already developed like Dijkstra's algorithm, Bellman-Ford algorithm or A* search algorithm.

The problem you face is also well described on Wikipedia.

Maybe there is something specific about your assignment like memory or time complexity?

• sorry i meant the shortest path graph... I dont know if this is exactly the same – Bobbbaa Dec 23 '12 at 20:32

As has been pointed out, there are well known shortest path algorithms. But your problem already has most of the information. Specifically, you already know the shortest path distances $d[v]$ from $s$ for each node $v$. In such a case, you can use a much better algorithm.

By a "shortest paths graph", I think you mean a collection of shortest paths from $s$ to every other vertex $v$. In such a case, you can use a Depth First Search (DFS) as follows:

• Start the DFS from the source vertex $s$.
• Mark a node visited as soon as you reach it for the first time.
• For every node $u$ visited, do a DFS on all children $v$ of $u$ only if $d[v] = d[u] + w(u, v)$, where $w(u, v)$ is the weight of the edge from $u$ to $v$.
• If a child $v$ of $u$, which obeys the previous condition of distances, has already been visited, it simply means that there are multiple shortest paths from $s$ to $v$, and that you have already selected some other such path which does not go through $u$. In such a case, do not include this edge $(u, v)$ in your shortest paths tree/graph. This is because by doing a DFS, you have already selected all shortest paths that go through $v$.

Note that this algorithm relies on the following property of a shortest path algorithm: edge $(u, v)$ is on some shortest path to $v$ from $s$ if and only if $d[v] = d[u] + w(u, v)$. Therefore, only the shortest paths are taken by the algorithm. Since we ignore a shortest path from $s$ to $v$ through $u$ if and only if $v$ has already been visited, we ensure that all shortest paths are included.

Note that this algorithm is linear in the size of the graph. I mention DFS, since it is much easier to program for such a scenario, and recursion holds the stack implicitly.

However, you can use BFS too for this purpose. Use the same property in the BFS as above, that is:

• Enqueue (and mark visited) only those neighbors $v$ of $u$ which obey the following property: $d[v] = d[u] + w(e, v)$.

Note that if there are multiple shortest paths to some vertex $v$ from $s$, using a DFS or a BFS may give different shortest path trees (though both will be correct). DFS will give a random tree, whereas BFS will give a tree where the shortest path selected would be such that it will also have the minimum number of edges among all shortest paths from $s$ to $v$. Unless you desire such a property, I think a DFS would be much simpler. See this Udacity nugget for more information about how to compare these algorithms and a more in depth explanation.

The best algorithm depends on whether $d[v]$ is reliable or not. If it is reliable then you can find the shortest paths graph like this:

for each edge e in G:
if weight[e] + d[origin of e] == d[end of e]:
include e in the output graph


If $d[v]$ is not reliable then Dijkstra's algorithm and the Bellman-Ford algorithm are best, and will also produce the correct values of $d[v]$ as a side effect.

EDIT

The graph produced by the above algorithm is not guaranteed to be a tree because of the possibility of equal cost paths. If you need it to be a tree, then you will need to use Edmonds's algorithm.

• This algorithm will include all parallel shortest paths from the source $s$ to any node $v$. Even though the OP is not very clear, he mentions a tree of edges, which probably indicates he wants a tree, and hence only one shortest path from source to every vertex must be included. – Paresh Dec 26 '12 at 4:31