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?

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 - eg 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 ...

    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 :)

    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.

    链接地址: http://www.djcxy.com/p/35292.html

    上一篇: 缺少给定边的最短路径

    下一篇: 图形中从单个源到单个目标的最短路径