Dijkstra's Algorithm (Greedy)
Find the shortest paths from a source vertex to all other vertices in a weighted graph (directed or undirected)
Dijkstra's Shortest Path Algorithm
Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph (directed or undirected) with non-negative edge weights using a greedy approach.
Theory & Concepts
Definition:
A greedy algorithm that finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Works with both directed and undirected graphs.
Key Points:
- Uses greedy approach - always selects the unvisited vertex with minimum distance
- Maintains a distance array and visited set
- Works only with non-negative edge weights
- Guarantees optimal solution for shortest path problems
Applications:
- GPS navigation and route planning
- Network routing protocols (OSPF)
- Social network analysis
- Game AI pathfinding
University Guidelines
Exam Weightage
8-10 marks MarksSyllabus Coverage:
- Dijkstra's algorithm implementation
- Shortest path problem formulation
- Greedy algorithm approach
- Time and space complexity analysis
- Comparison with other shortest path algorithms
Common Questions:
- Implement Dijkstra's algorithm
- Find shortest paths from given source
- Show step-by-step execution
- Create distance and predecessor tables
Exam Tips:
Always maintain distance and visited arrays
Show table with each iteration clearly
Mark visited nodes and update distances
Include final shortest path tree
Algorithm Details
O(V²) with simple array, O((V + E) log V) with priority queue
Time Complexity
O(V) for distance and visited arrays
Space Complexity
Algorithm Steps:
- 1Initialize distances: source = 0, others = ∞
- 2Mark all vertices as unvisited
- 3Select unvisited vertex with minimum distance
- 4Update distances to all adjacent unvisited vertices
- 5Mark current vertex as visited
- 6Repeat until all vertices are visited
Draw Your Graph
Instructions:
- Toggle between Undirected graph mode
- Click "Add Node" then click on canvas to add vertices
- Add Edge: Click "Add Edge", set weight, then click two nodes to connect them
- Undirected edges connect both ways automatically
- The first node will turn yellow when selected, then click the second node
- Click "Delete" then click nodes to remove them
- Drag nodes to move them around (not available in edge mode)
- Use Undo/Redo to restore accidentally deleted items
- Select source node and run the algorithm
Algorithm Results
🗺️
Draw a graph and click "Run Dijkstra's Algorithm" to see the shortest paths