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
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence