This is a tool to help you visualize how the algorithms, used for solving Shortest Path Problem, work.
The shortest path problem in graph theory, is a Combinatorial Optimization problem. The problem requires one to find a path between a source and a destination, such that travelling through the found path, costs the least. For the sake of problem-solving, this problem is interesting enough to try and solve. However, what makes this, one of the most-studied combinatorial optimization problem is the real life scenarios, that deal with this problem, as their primary application or as a subproblem of their primary application. Below are a few examples of such real life scenarios:
- Finding Shortest Path between two places in applications like GPS-enabled Google Maps, Waze.
- Used in IP routing. IP routing uses Open Shortest Path First (OSPF) routing protocol, that uses a shortest path problem solving algorithm named as Dijkstra's algorithm.
- Communication Networks use shortest path problem solving algorithms to minimize network wide cost and regulate network traffic flows.
Over the time, various algorithms has been conceived to solve the shortest path problem. These algorithms both have their own advantages and disadvantages depending on the applications, they are used in. Here, however, only few of them has been implemented for visualization. These are:
- BFS(Breadth First Search)
- Dijkstra's Algorithm
- Bellman Ford Algorithm
- Floyd Warshall Algorithm
