Dijkstra's Algorithm

The algorithm operates by greedily selecting the unvisited node with the smallest known distance from the source. This is implemented efficiently using a priority queue (often a min-heap), which allows for O(log V) retrieval and update operations. At each step, this node is considered 'settled,' meaning its shortest path is guaranteed to be found. The algorithm then relaxes the edges from this node, updating the distances to its neighbors if a shorter path is discovered.

• Core Operation: extract-min from the priority queue.
• Complexity: The use of a binary heap leads to a time complexity of O((V + E) log V), where V is vertices and E is edges.

Dijkstra's Algorithm provides a mathematical guarantee of finding the single-source shortest paths for graphs with non-negative edge weights. This optimality proof relies on the invariant that once a node is extracted from the priority queue (settled), the distance assigned to it is the shortest possible. The presence of any negative edge weight violates this invariant, as a later, cheaper path could be found through a previously settled node, potentially leading to incorrect results.

• Key Assumption: All edge weights must be ≥ 0.
• Contrast: For graphs with negative weights, algorithms like Bellman-Ford must be used.

Unlike point-to-point algorithms like A* Search, Dijkstra's solves the single-source shortest path problem. It computes the shortest path from one chosen source node to every other node in the graph. This makes it exceptionally useful for applications like network routing protocols (e.g., OSPF) where a router needs to know the best path to all possible destinations.

• Output: A shortest-path tree rooted at the source node.
• Memory: Requires storing a distance and predecessor for every vertex (O(V) space).

The algorithm's correctness critically depends on the constraint that all edge weights are non-negative. This is not merely a limitation but a foundational requirement for its greedy proof of optimality. If a negative weight cycle is reachable from the source, the concept of a 'shortest path' may be undefined (infinite negative loop). For environments with potential negative costs, this constraint must be strictly validated before application.

• Practical Implication: Ideal for physical distances, network latency, or monetary costs, but not for financial arbitrage or similar problems.

The time complexity of Dijkstra's Algorithm depends on the data structure used for the priority queue. The standard implementation using a binary min-heap results in O((V + E) log V) time, where V is the number of vertices and E is the number of edges. Using a more advanced Fibonacci heap can theoretically reduce this to O(E + V log V), though with higher constant factors. Its space complexity is O(V) to store distances, predecessors, and the queue.

• Comparison: More efficient than Bellman-Ford (O(VE)) for non-negative graphs, but less targeted than A* for point-to-point search with a good heuristic.

Dijkstra's Algorithm is a direct precursor to other key search algorithms. Uniform-Cost Search (UCS) is essentially Dijkstra's Algorithm applied to an implicit graph (like a tree). More significantly, A Search* can be viewed as Dijkstra's with an added heuristic function h(n) that guides the search toward a specific goal. When the heuristic h(n) = 0 for all nodes, A* behaves identically to Dijkstra's. Understanding Dijkstra's is therefore essential for grasping the mechanics and guarantees of these more advanced algorithms.

Uniform-Cost Search (UCS) is the un-informed counterpart to Dijkstra's Algorithm. It is a graph search algorithm that expands the node with the lowest path cost from the start node, guaranteeing an optimal solution when all step costs are non-negative.

• Key Difference: UCS uses a simple cost-from-start metric (g(n)), while Dijkstra's is the specific, efficient implementation of this principle using a priority queue.
• Guarantee: Both guarantee optimality in graphs with non-negative weights.
• Use Case: UCS is a fundamental concept for understanding optimal search in weighted graphs before introducing heuristics.

A Search* is a best-first, heuristic-guided extension of Dijkstra's Algorithm. It finds the lowest-cost path by combining the actual cost to reach a node (g(n), as in Dijkstra's) with a heuristic estimate of the remaining cost to the goal (h(n)).

• Formula: f(n) = g(n) + h(n). When h(n) = 0, A* degenerates to Dijkstra's Algorithm.
• Admissibility: For optimality, the heuristic must be admissible (never overestimates the true cost).
• Efficiency: A* is often more efficient than Dijkstra's because the heuristic focuses the search towards the goal, exploring fewer nodes.

The Bellman-Ford Algorithm solves the single-source shortest path problem, like Dijkstra's, but can handle graphs with negative edge weights. It operates by relaxing all edges repeatedly, for |V|-1 iterations.

• Key Contrast: Dijkstra's fails with negative weights; Bellman-Ford can detect negative-weight cycles.
• Trade-off: Bellman-Ford's time complexity is O(|V|*|E|), which is higher than Dijkstra's O(|E| + |V|log|V|) with a priority queue.
• Use Case: Essential for financial arbitrage networks or any system where transitions can have negative costs.

A Priority Queue, typically implemented as a min-heap, is the critical data structure that enables Dijkstra's Algorithm's efficiency. It maintains the frontier of nodes to be explored, ordered by their current tentative distance.

• Operation: Supports insert, decrease_key, and extract_min operations in O(log n) time.
• Role in Dijkstra's: The algorithm's O(|E| + |V|log|V|) complexity relies on the heap for efficient selection of the next node with the smallest known distance.
• Variants: Fibonacci heaps can offer better amortized time for decrease_key, but binary heaps are most common in practice.

A Heuristic Function, h(n), estimates the cost from a node n to the goal. While Dijkstra's Algorithm uses no heuristic (h(n)=0), understanding heuristics is key to grasping more advanced algorithms like A* that build upon it.

• Purpose: To guide search algorithms towards the goal more efficiently than uninformed search.
• Admissible vs. Consistent: An admissible heuristic never overestimates true cost. A consistent (or monotonic) heuristic satisfies the triangle inequality, guaranteeing A* finds an optimal path without re-processing nodes.
• Example: In pathfinding on a grid, the straight-line (Euclidean or Manhattan) distance to the goal is a common heuristic.

Dijkstra's Algorithm operates on a weighted directed graph G = (V, E, w). This fundamental data structure defines the problem space.

• Vertices (V): Represent states, locations, or decision points (e.g., network routers, map intersections).
• Edges (E): Represent possible transitions or actions between states.
• Weight Function (w): Assigns a non-negative cost to each edge, representing distance, latency, or penalty for that transition.
• Assumption: The algorithm requires non-negative edge weights. This graph model is ubiquitous in networking, logistics, and state-space planning for agents.