Shortest path from single source to single destination in a graph
Solution 1
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 ...
Solution 2
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 :)
Solution 3
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.
ravi
Updated on April 28, 2020Comments
-
ravi about 4 years
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 usingDijkstra'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
. Bybidirectional bfs
i mean to apply twobfs
one fromsource node
, another one fromdestination node
. As soon as for the first time when i find any samechild
in both tree,i can stop bothbfs
.Now the path from source to that childunion
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? -
ravi about 12 yearsmy graph contains positive weights
-
ravi about 12 yearsI didn't get your logic.
Dijkstra's algorithm
always pick that edge which is shortest.