Given a weighted graph, find the shortest path from a starting vertex to all other vertices.
Can select any vertex as the source.
Minimization problem (optimization problem).
Solved by the greedy method.
Greedy Method
Concept: Solve problems in stages, taking one step at a time and considering one input at a time to get an optimal solution.
There are predefined procedures to follow.
Dijkstra's algorithm provides a procedure to get the minimum result (shortest path).
Basics of Dijkstra's Algorithm
Example: Small graph with vertices 1, 2, and 3 to explain the approach.
Direct path from 1 to 2 with cost 2.
No direct path from 1 to 3 initially.
**Process: **Select the vertex with the shortest path first, then update the shortest path to other vertices if possible.
Relaxation: The process of updating the shortest path estimate.
For a vertex u with distance d[u] and a vertex v with distance d[v] and edge cost c(u, v), if d[u] + c(u, v) < d[v], then update d[v] = d[u] + c(u, v).
Example Walkthrough
Graph: Vertices 1 to 6.
Steps:
Set initial distances.
Distance from 1 to itself is 0.
Distance from 1 to 2 is 2; from 1 to 3 is 4; others are infinity.
Repeatedly select the shortest path and perform relaxation.
Select shortest vertex, perform relaxation for connected vertices, and update distances.
Continue this until all vertices are processed.
Final distances from vertex 1:
1 to 2: 2
1 to 3: 3
1 to 4: 8
1 to 5: 6
1 to 6: 9
Time Complexity Analysis
**Steps: **Finding the shortest path for all vertices and performing relaxation.
Number of vertices:n
May relax all vertices in complete graphs.
Worst-case time complexity: O(n^2).
Algorithm on a Weighted Directed Graph
Example: Weighted directed graph.
**Steps: **Use a table to record distances and perform selections and relaxations.
Final result: Calculates shortest paths from the source vertex to all others, but can result in infinity if vertices are unconnected.
Working on Non-Directed Graphs
Can work on undirected graphs by converting them to directed graphs by adding parallel edges.
Drawback of Dijkstra's Algorithm
Negative Weighted Edges: Algorithm may not work correctly if there are negative weighted edges.
Example: Worked with -3 in an edge, provided the wrong shortest path.
Reason for Failure: Greedy approach doesn’t consider all possibilities; it selects the apparent minimum immediately.
Solution: Use of Bellman-Ford algorithm for graphs with negative weights.
Conclusion
**Summary: **Dijkstra's algorithm for single source shortest path and its greedy approach.
Next Step: Explore Bellman-Ford algorithm in dynamic programming.
Invite comments and suggestions for future improvements.