CODEWITHSUNDEEP
algorithmgraphshortest-path
Berial
Berial

Reputation: 557

shortest paths not path in graph

I was wondering if there is an algorithm which would find shortest paths in graph.

Let's say that I have a graph where there are couples of path from one vertex to another. Two or more of these paths have the same cost. How can I mark, find etc all shortest paths between these vertices ? As far as I know Dijkstra or Bellman-Ford algorithms will find shortest path but they "choose" only one.

Upvotes: 1

Views: 961

Answers (2)

T.K.
T.K.

Reputation: 2259

Take a look at Floyd-Warshall.

In computer science, the Floyd–Warshall algorithm (sometimes known as the WFI Algorithm or Roy–Floyd algorithm) is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. The algorithm is an example of dynamic programming.

Upvotes: 0

deinst
deinst

Reputation: 18772

Dijkstra's algorithm gives you the cost to all the possible intermediate nodes, and the cost of the shortest path to the sink. You can get all the paths from source to sink by doing a depth first search from the sink to the source (going backwards), where you traverse an edge (backwards) only if the cost of that edge is equal to the difference between cost of the shortest path from the source to the two nodes. Of course you get the paths in reverse order, but reversing them is easy.

.

Upvotes: 2

Related Questions