Please search "Dijkstra" algorithm. Our network module package ClustEx include two fast algorithms: Eppstein (for non-simple paths) & KSP (for simple paths without loops). http://bioinfo.au.tsinghua.edu.cn/member/jgu/clustex/

We can calculate shortest path using different techniques:

1. using knapsack algorithm (for complete explanation you can refer http://www.diku.dk/~pisinger/95-1.pdf )

2. some other methods are available on the following given addresses

http://cgi.csc.liv.ac.uk/~ped/teachadmin/algor/greedy.html

http://www.civil.uwaterloo.ca/itss/papers%5C2006-3%20%28Review%20of%20heuristic%20SPA%29.pdf

You can also look into optimized algorithms for graph search like A* or even D*.

http://en.wikipedia.org/wiki/A*_search_algorithm

http://en.wikipedia.org/wiki/D*

By the way, a nice online app that compares search techniques:

http://qiao.github.io/PathFinding.js/visual/

The shortest path in a connected graph can be calculated using many techniques such as Dikshatra' s algorithm. Other techniques such as Backtracking through tree search techniques like Depth first Search Tree and Breadth First Tree approaches.

Thanking you,

the most common algorithms are:

"1- Dijkstra's algorithm solves the single-source shortest path problem.

2- Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.

3- A* search algorithm solves for single pair shortest path using heuristics to try to speed up the search.

4- Floyd–Warshall algorithm solves all pairs shortest paths.

5- Johnson's algorithm solves all pairs shortest paths, and may be faster than Floyd–Warshall on sparse graphs.

6- Viterbi algorithm solves the shortest stochastic path problem with an additional probabilistic weight on each node." source: wikipedia