Dijkstra
Single-Pair Shortest Path: Finding shortest path between nodes in a graph.
Single-Source Shortest Path: "source" node + find shortest paths from the source to all other nodes in a graph, producing shortest-path tree
Assumption
- the graph is connected
- the edges are directed
- the edges are non-negative
Input: weighted graph and the source vertex
Output: lengths of the shortest paths from the given source vertex to all other vertices
Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.
Dijkstra is a greedy algorithm by choosing the 'lightest' path every time.
Dijkstra’s doesn’twork when there are negative edges:
–Intuition–we can not be greedy any more on the assumption that the lengths of paths will only increase in the future
Single-Pair Node Procedures
Single-Source Node Procedures
1 function Dijkstra(Graph, source):
2
3 create vertex set Q
4
5 for each vertex v in Graph: // Initialization
6 dist[v] ← INFINITY // Unknown distance from source to v
7 prev[v] ← NULL // Previous node in optimal path from source
8 add v to Q // All nodes initially in Q (unvisited nodes)
9
10 dist[source] ← 0 // Distance from source to source
11
12 while Q is not empty:
13 u ← vertex in Q with min dist[u] // Node with the least distance
14 // will be selected first
15 remove u from Q
16
17 for each neighbor v of u: // where v is still in Q.
18 alt ← dist[u] + length(u, v) // alt: new distance value
19 if alt < dist[v]: // A shorter path to v has been found
20 dist[v] ← alt
21 prev[v] ← u
22
23 return dist[], prev[]