Dijkstra's Algorithm
# Dijkstra’s Algorithm
Shortest Path Problem Find the shortest path from source to all other vertices.
Adding a positive constant to all edges Dijkstra finds the shortest path in terms of the edge weights and not the number of edges. Hence, the shortest path may contain many edges. This means that a change in edge weights will result in a different shortest path unless the number of edges in each path is the same.
Multiplying all edges by a positive constant
This leads to a contradiction as Q is now a shorter path than P but P is the shortest path in G.
Assumptions: Weights must be nonnegative
# Data Structures Needed
# Pseudocode
We can also obtain the number of distinct shortest paths by using an additional n-size array to store the counts of paths which have the same shortest distance:
# Proof of Correctness
Why the greedy choice is optimal:
This step is the reason for why graphs with negative weights do not ensure correctness of Dijkstra’s .
# Examples
Manually computing shortest path:
