dijkstra-s-algorithm.md (1100B)
1 +++ 2 title = "Dijkstra’s algorithm" 3 template = "page-math.html" 4 +++ 5 6 # Dijkstra’s algorithm 7 8 Problem 9 10 Shortest path from single source to all others (unlike Computer Networks, which was between two nodes) 11 12 Solution 13 S = {}, Q = {all vertices} 14 distance to every node is infinity, path to every node is nil 15 16 extract the one with shortest distance from Q (source) 17 add it to S 18 for each neighbour of extracted node (relax function): 19 20 - if its distance is greater than weight of going to it, 21 - update its distance to (distance of extracted node + weight of edge to neighbour) 22 - update its path to the extracted node 23 24 Complexity 25 initialize in ϴ(|V|) 26 init S in constant time 27 init Q: build priority queue using insert 28 while loop: 29 30 - |V| times extract-min 31 - |V| times update of S (constant time) 32 33 for loop executed in total |E| times with inside update key of v 34 35 depends on how priority queue is implemented: 36 37 - array: extract-min takes |V| steps, so algorithm in $O(|V|^2+|E|)=O(|V|^2)$ 38 - heap: extract-min in O(log|V|), so algorithm in $O((|V|+|E|)\log{|V|})=O(|E|\log{|V|)$ (more edges than vertices)