CODEWITHSUNDEEP
algorithmshortest-path
ravi
ravi

Reputation: 6328

Shortest path from single source to single destination in a graph

My graph contains no such edges which connect a vertex to itself. There is only one edge between two vertices. From Wikipedia i got to know about some algorithm which are used for calculating shortest path based on the given conditions. One of the most famous algorithm is Dijkstra's algorithm, which finds a shortest paths from source vertex to all other vertices in the graph.
But by using Dijkstra's algorithm, i am unnecessary exploring all the vertices, however my goal is just to find shortest path from single source to single destination. Which strategy should i use here? So that i need not to explore all other vertices.

One of my approach is to use bidirectional bfs. By bidirectional bfs i mean to apply two bfs one from source node, another one from destination node. As soon as for the first time when i find any same child in both tree,i can stop both bfs .Now the path from source to that child union path from child to destination would be my shortest path from source to destination.

But out of all the approaches described by Wikipedia and bidirectional bfs, which one suits best for my graph?

Upvotes: 5

Views: 29622

Answers (4)

Viktor Nordling
Viktor Nordling

Reputation: 9284

The Wikipedia article spells out the answer for you:

If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 13 if u = target.

Upvotes: 2

bubersson
bubersson

Reputation: 829

It depends if there's any apparent heuristic function that you could use or if you don't have any further usable information about your graph.

Your options are:

  • BFS: in general case or if you don't care about computation time that much.
  • Dijkstra (Dijkstra "is" BFS with priority queue): if your edges have weights/prices (non negative) and you care about CPU time.
  • A* (A* "is" Dijkstra with heuristic function - e.g. distance on a city map): if you want it to be really fast in average case, but you have to provide good heuristic function.

For some graph problems it may be possible to use Dynamic programming or other algorithmic tools. It depends on a situation. Further information can be found in tutorials from http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index ...

Upvotes: 6

DerMike
DerMike

Reputation: 16180

You could use Dijkstra's algorithm and optimize it in the way that you stop exploring paths that are already longer than the shortest you found so far. Because those are not going to be shorter (provided that you don't have negative weighs on your edges).

Upvotes: 0

Priyank Bhatnagar
Priyank Bhatnagar

Reputation: 814

From Introduction to Algorithms (CLRS) second edition, page 581 :

Find a shortest path from u to v for a given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. Moreover, no algorithms for this problem are known that run asymptotically faster than the best single-source algorithms in the worst case.

So, stick to Dijkstra's algorithm :)

Upvotes: 1

Related Questions