Shortest path algorithms.md (2129B)
1 +++ 2 title = 'Shortest path algorithms' 3 +++ 4 # Shortest path algorithms 5 Arcs in digraphs may carry negative weights. if there’s a cycle of negative weight, there are no shortest paths. Otherwise, there might be. 6 7 Dijkstra’s (non-negative weights) 8 9 - used for link-state routing 10 - fails if there are negative weights 11 - to implement efficiently, you need Fibonacci heap data structure 12 - the goal is shortest path to a node from every other node 13 - algorithm (given that c is goal): 14 15 1. Svisited = {}, Hunvisited = {a,b,…}, Cgoal(0, F) 16 17 - add goal to visited, remove from unvisited 18 - S = {c} 19 - H = {a,b,d,e,f,g,h} 20 - find neighbours of added node that have edges pointing to it — b(1,c), e(2,c) 21 - choose lowest weight edge, add that node into visited set — b(1,c) 22 - current distances: 23 - b(1,c) 24 25 2. S = {b,c}, H = {a,d,e,f,g,h} 26 27 - find neighbours of added node that have edges pointing to it —a(2,b),c(1,b) 28 - c is visited, no other neighbours, so select a. 29 - add a to set, update distance. 30 - distance to c = b(1,c) + (distance a=>b) = b(1,c)+a(2,b) = a(3,c) 31 - current distances: 32 - b(1,c) 33 - a(3,c) 34 35 3. S = {a,b,c}, H = {d,e,f,g,h} 36 37 - find neighbours of added node that have edges pointing to it —b(2,a), d(1,a) 38 - b is visited, no other neighbours, so select d. 39 - add d to set, update distance. 40 - distance to c = a(3,c) + (distance d=>a) = a(3,c) + d(1,a) = d(4,c) 41 - current distances: 42 - b(1,c) 43 - a(3,c) 44 - d(4,c) 45 46 4. S = {a,b,c,d}, H = {e,f,g,h} 47 48 - etc. 49 50 Bellman-Ford algorithm 51 52 - allows weights to be negative 53 - max n-1 iterations (with checking for negative cycle) 54 - computes shortest path in rounds. each round tells you how many edges you can walk to reach the goal. 55 - [this one is best explained with a video, which shows how to fill in one of the rows (you just have to make one row for each node)](https://www.youtube.com/watch?v=obWXjtg0L64&index=8&list=PL8WcC83XRlKJHk_bQLE-mEQRvdpflxHG2)