Dijkstra's Algorithm - Technical Overview
1. Algorithm Description: Dijkstra's Algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights.
2. Steps of Dijkstra's Algorithm:
- Initialize distances from the source to all nodes as infinity, except the source itself (which is 0).
- Mark all nodes as unvisited. Set the source node as the current node.
- For the current node, consider all its unvisited neighbors and calculate their tentative distances through the current node.
- Update the shortest distance if the calculated distance is less than the current stored distance.
- Once all neighbors have been considered, mark the current node as visited.
- Select the unvisited node with the smallest tentative distance and set it as the new current node. Repeat until all nodes are visited.
3. Time Complexity: O((V + E) log V) where V is the number of vertices and E is the number of edges.
4. Space Complexity: O(V) due to the storage of distances and visited nodes.
5. Usage: Dijkstra's Algorithm is commonly used in routing and as a subroutine in other graph algorithms.