Topic: Dijkstra's Algorithm for the Single Source Shortest Path Problem
Purpose: To find the shortest path from a given source vertex to all other vertices in a graph.
Key Concept: Single source, where one vertex is the starting point (e.g., vertex 0).
Working Principle of Dijkstra's Algorithm
Initialization:
Set the distance to the source vertex (0) to 0.
Set the distance to all other vertices to infinity.
Selection of Vertex:
Start from the source vertex (e.g., vertex 0).
For each vertex directly connected to the selected vertex, update their distances if the new calculated distance is less than the previously recorded distance.
Use the formula: distance(V) = distance(U) + cost(U to V)
Example Updates:
From 0 to 1: 0 + 4 = 4 (update distance of vertex 1 from infinity to 4)
From 0 to 4: 0 + 8 = 8 (update distance of vertex 4 from infinity to 8)
Repeat Selection:
Select the next unvisited vertex with the shortest distance.
Mark the current vertex as visited.
Repeat the update process for the newly selected vertex.
Continue until all vertices have been visited.
Final Distances:
After all vertices are visited, the shortest distances from the source to all vertices can be recorded.
Example Walkthrough
Consider a graph and find shortest paths from vertex 0:
Shortest distance from 0 to:
3: 19
8: 14
6: 11
7: 21
5: 9
4: 8
1: 4
2: 12
Dijkstra's Algorithm with Directed Graphs
The same principles apply when working with directed graphs.
Use a table to update distances for clarity.
Example with vertex A as the source:
Finding Shortest Paths
To find the path along with the distance:
Set a pointer to the shortest distance.
Backtrack through the selected vertices to reconstruct the path.
For instance, from A to D:
The path might be A -> C -> B -> D.
Verify distances using the graph.
Drawbacks of Dijkstra's Algorithm
Key Limitation: Dijkstra's algorithm does not work properly with graphs that contain negative edge weights.
Example: If edges have negative weights or cycles with negative weights, the algorithm can yield incorrect results.
The algorithm may produce a shortest distance that is not accurate due to the inability to update distances of already visited vertices.
Conclusion
Dijkstra's algorithm is effective for graphs with non-negative weights but fails in cases with negative edge weights or negative cycles.
Important to consider these factors when using the algorithm in practical applications.
Next Steps
Further study and examples of algorithms suitable for graphs with negative weights (e.g., Bellman-Ford algorithm).