Shortest paths graph

Question

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?

Answer 1

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?

Answer 2

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.

Answer 3

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.