Shortest Path Calculator

Find shortest paths in graphs using Dijkstra's, Bellman-Ford, Floyd-Warshall, and A* algorithms

Start Node
End Node
Path Node
Shortest Path

Algorithm Selection

Choose the shortest path algorithm to use

Dijkstra's Algorithm

Finds shortest paths from a source node to all other nodes in weighted graphs with non-negative edges.

O(E log V)
A* Search Algorithm

Uses heuristics to find the shortest path more efficiently. Best for grid-based pathfinding.

O(bᵈ)
Bellman-Ford

Handles graphs with negative weight edges and detects negative cycles.

O(VE)
Floyd-Warshall

Finds shortest paths between all pairs of nodes. Works with negative weights.

O(V³)

Shortest Path Algorithms Explained

What is a shortest path problem? In graph theory, the shortest path problem involves finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Algorithm Comparison

Algorithm Best For Time Complexity Space Complexity Edge Weights
Dijkstra's Single-source shortest path, non-negative weights O(V²) or O(E log V) O(V) Non-negative only
A* Search Pathfinding with heuristics, grids, maps O(bᵈ) - depends on heuristic O(V) Non-negative only
Bellman-Ford Graphs with negative weights, detecting negative cycles O(VE) O(V) Any weights
Floyd-Warshall All-pairs shortest paths, dense graphs O(V³) O(V²) Any weights (no negative cycles)

Real-World Applications

1

Navigation Systems: GPS and map applications use shortest path algorithms to find the fastest route between locations.

2

Network Routing: Internet protocols use shortest path algorithms to route data packets through networks efficiently.

3

Robotics: Path planning for autonomous robots and drones to navigate through environments.

4

Game Development: AI characters use pathfinding to navigate game worlds and reach targets.

Frequently Asked Questions

Dijkstra's algorithm explores all directions equally, while A* uses a heuristic to prioritize nodes that seem closer to the destination. A* is generally faster for single-pair shortest path problems when a good heuristic is available, but Dijkstra's guarantees the shortest path in all cases with non-negative weights.

Dijkstra's and A* cannot handle negative weight edges correctly. Bellman-Ford can handle negative weights and detect negative cycles. Floyd-Warshall can handle negative weights but not negative cycles (cycles where the total weight is negative).

Use Floyd-Warshall when you need to find shortest paths between all pairs of nodes. It's particularly useful for dense graphs where you need many shortest path queries. For single-source problems, Dijkstra's or Bellman-Ford are more efficient.

The visualization uses vis.js library to render an interactive graph. You can add nodes by clicking "Add Node", add edges by selecting two nodes, and drag nodes to rearrange the graph. The shortest path is highlighted in green once calculated.