Shortest Path Algorithms

Dijkstra's algorithm is a classic, single-source shortest path algorithm for graphs with non-negative edge weights. It operates by iteratively exploring the nearest unvisited node from the source, using a priority queue for efficiency.

• Core Mechanism: Maintains a tentative distance for each node. At each step, it selects the node with the smallest tentative distance, finalizes it, and relaxes (updates) distances to its neighbors.
• Time Complexity: O((V + E) log V) with a binary heap, where V is vertices and E is edges.
• Primary Use Case: Finding the shortest driving routes in road networks (where distances are non-negative).
• Limitation: Cannot handle graphs with negative edge weights, as this can cause incorrect results.

The Bellman-Ford algorithm solves the single-source shortest path problem and can handle graphs with negative edge weights. It detects negative weight cycles reachable from the source, which would allow for infinitely decreasing path costs.

• Core Mechanism: Relaxes all edges repeatedly (for V-1 iterations, where V is the number of vertices). A final pass checks for negative cycles.
• Time Complexity: O(V * E), making it slower than Dijkstra for typical cases.
• Primary Use Case: Routing in networks where link costs can be negative (e.g., certain financial arbitrage models) or for cycle detection.
• Key Feature: Its robustness with negative weights makes it a foundational component in distance-vector routing protocols.

A Search* is an informed, best-first search algorithm that finds the shortest path between a start and goal node. It uses a heuristic function to estimate the cost to the goal, prioritizing exploration of the most promising paths.

• Core Mechanism: Evaluates nodes using the function f(n) = g(n) + h(n), where g(n) is the cost from the start node, and h(n) is a heuristic estimate to the goal. It uses a priority queue sorted by f(n).
• Optimality: Guaranteed to find the shortest path if the heuristic is admissible (never overestimates the true cost) and consistent.
• Primary Use Case: Pathfinding in video games, robotics, and geographical maps (e.g., using Euclidean distance as a heuristic).
• Advantage: Often significantly faster than Dijkstra's by directing the search towards the target.

The Floyd-Warshall algorithm is an all-pairs shortest path algorithm. It computes the shortest paths between every pair of vertices in a weighted graph, which can be directed and can have negative weights (but no negative cycles).

• Core Mechanism: Employs dynamic programming. It iteratively considers each vertex as a potential intermediate node to improve path estimates between all other pairs.
• Time Complexity: O(V³), making it practical only for graphs with a few hundred to a few thousand vertices.
• Output: Produces a distance matrix and a predecessor matrix for path reconstruction.
• Primary Use Case: Precomputing path costs for dense graphs in network analysis, computing the transitive closure, and solving related graph problems.

Breadth-First Search (BFS) is the optimal algorithm for finding the shortest path in an unweighted graph, where all edges have an implicit, equal cost (e.g., one hop).

• Core Mechanism: Explores the graph level by level from the source node using a queue. The first time a node is discovered, the path to it is guaranteed to be the shortest in terms of the number of edges.
• Time Complexity: O(V + E) for an adjacency list representation.
• Path Metric: Minimizes the number of edges (hop count), not a sum of weights.
• Primary Use Case: Finding the minimum number of connections in social networks, shortest link path in computer networks, and solving puzzles like the classic "water jug" problem.

Johnson's algorithm is an efficient method for computing all-pairs shortest paths in sparse graphs that may contain negative weights (but no negative cycles). It combines Bellman-Ford and Dijkstra's algorithms for superior performance.

• Core Mechanism:
  1. Adds a new source node connected to all others with zero-weight edges.
  2. Runs Bellman-Ford from this node to compute a potential (h(v)) for each vertex, used to reweight all edges to non-negative values.
  3. Runs Dijkstra's algorithm from each original vertex using the reweighted graph.
• Time Complexity: O(V E log V) with a binary heap, which is better than Floyd-Warshall's O(V³) for sparse graphs.
• Primary Use Case: All-pairs shortest path calculations in large, sparse networks where edge weights can be negative, such as in certain financial or circuit analysis applications.