Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers 3

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?

share|improve this answer
    
sorry i meant the shortest path graph... I dont know if this is exactly the same –  Bobbbaa Dec 23 '12 at 20:32
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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