Shortest paths graph

Question

Given a directed graph G , weights, s source vertex 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 than how can I know which edge should be in the tree and how to check that the d[v] for each vertex is true.

By "shortest paths tree", do you mean the minimum spanning tree? — Vaughn Cato
– Vaughn Cato, Commented Dec 23, 2012 at 20:00
@VaughnCato: I think he means Dijkstra, which gives the shorted path from the source vertex to every other vertex. Though I'm not sure what makes it a "tree"... — user541686
– user541686, Commented Dec 23, 2012 at 20:02
What is the measurement for the length of the path? The sum of the edge weights? If so, then d[v] seems redundant. — Vaughn Cato
– Vaughn Cato, Commented Dec 23, 2012 at 20:06
@VaughnCato question says - d[v] is the distance (in weight) of every vertex v from s — Bobbbaa
– Bobbbaa, Commented Dec 23, 2012 at 20:08
I need to use that and than to also check that its values are true according to the given weights — Bobbbaa
– Bobbbaa, Commented Dec 23, 2012 at 20:09

bcurcio · Accepted Answer · 2012-12-23 20:15:39Z

3

Run Dijkstra. If an edge e connecting {u,v} has the property that d[u]+w[e]=d[v] then that edge is part of the tree you are looking for.

This way, you may not actually end up with a tree, but any MST has the properties you are looking for

answered Dec 23, 2012 at 20:15

bcurcio

5482 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Bobbbaa Over a year ago

and if im just going through the edges using BFS and checking if d[u]+w[e]=d[v] ? why do I need to use Dijkstra?

Patricia Shanahan Over a year ago

@Bobbbaa A BFS may use a node as a source node before finding the lowest weight path to it. Remember an indirect path via several other nodes may have lower total weight than a single edge.

Programmer · Accepted Answer · 2012-12-23 21:13:57Z

3

The BFS algorithm helps you find the shortest path between a given root node and all other nodes only for an unweighted graph (or all weights are the same). If each edge has different weights, then the Dijkstra algorithm is a good choice. However, the Dijkstra algorithm does not work if there are are negative weights in the graph. If there are negative weights, then you should use the Bellman ford algorithm.

answered Dec 23, 2012 at 21:13

Programmer

6,78330 gold badges81 silver badges130 bronze badges

Collectives™ on Stack Overflow

Shortest paths graph

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related