What's the simplest algorithm/solution for a single pair shortest path through a real-weighted undirected graph?
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
Overview
Finding the shortest path between two nodes in a weighted, undirected graph is a classical problem in computer science. Whether applied in network routing, navigation systems, or project management, finding efficient solutions is essential. The simplest and most widely used algorithm for finding the shortest path in such graphs is Dijkstra's Algorithm.
This article breaks down Dijkstra's Algorithm, explains its mechanics, explores its complexities, and provides insights into its applications.
Dijkstra's Algorithm
Background
Dijkstra's Algorithm, conceived by Edsger W. Dijkstra in 1956, is designed to find the shortest path from a source vertex to a target vertex in a graph where the edges have non-negative weights.
Key Steps
- Initialization:
- Assign a tentative distance value to every vertex: zero for the initial vertex and infinity for all others.
- Set the initial node as the current node and mark all others as unvisited.
- Settle the Current Node:
- From the current node, consider all its unvisited neighbors. Calculate their tentative distances from the initial node through the current node.
- Update the tentative distance of each neighbor if the calculated distance is less than the recorded value.
- Mark as Visited:
- Once all of the neighbors' tentative distances of a current node are considered, mark the current node as visited. A visited node will not be checked again.
- Select Next Node:
- Select the unvisited node with the smallest tentative distance and set it as the "current node".
- Repeat:
- Continue the process until the destination node is marked visited or until no unvisited nodes with finite tentative distance remain.
Pseudocode
- A to B: 4
- A to C: 2
- B to C: 5
- B to D: 10
- C to D: 3
- D to E: 4
- C to E: 1
- A: 0
- B: ∞, C: ∞, D: ∞, E: ∞.
- B: 4, C: 2.
- C to D: 2 + 3 = 5
- C to E: 2 + 1 = 3
- Bidirectional Dijkstra: Runs two simultaneous searches from the source and target, which meet in the middle.
- A Search*: Uses heuristics to enhance search efficiency, often employed in pathfinding problems where optimality isn't strictly necessary.
