Dijkstra

NutshellSingle source algorithm Finds shortest paths to every other node on a weighted graph in O ( (|E|+|V|) * log(|V|)) Heap-del-min is called V times and its time complexity is log V. Heap-decrease-key kutsutaan jokaiselle kaarelle, E * log(V). Alustus O(E+V)

Adj-lists (building Graph) Single source initialization (all added to heaps, distances to inf, path[v]=NIL Call remove min, go through all the adj list vertices, RELAX them. repeat 3 until heap is empty.