Shortest path problem

The shortest path problem try to find a path in a graph cover the less distance. For that, the weights of the chosen edges should be as small as possible.

If you need to pass by all the vertices, it becomes a Traveling Salesman problem.

Algorithms

• A* search algorithm use heuristics to try to speed up the search.
• Bellman-Ford algorithm can find a path even with negative edges.
• Dijkstra algorithm finds a single path, but the edges should have non-negative weights.
• Floyd-Warshall algorithm solves all pairs shortest paths.