# Dijkstra's Algorithm **An algorithm for finding the [[Shortest Path Problem|shortest path]] from a source vertex to every other vertex in a non-negative [[Graph#Weighted graph|weighted graph]].** ![[Dijkstra'sAlgorithm1.svg|700]] *** ![[Dijkstra'sAlgorithm2.svg|700]] *Dijkstra's algorithm on a graph; previously assigned distances are updated if a newly calculated distance is lower* ***Worst-case [[time complexity]]:*** $O(E+V\log V)$ > [!Algorithm] > 1. Initialise all vertices as unvisited and form a set of unvisited vertices. > 2. Assign a distance to every vertex from the source vertex. For all vertices besides the source, assign their distance as infinity. The source vertex has a distance of zero. > 3. For the vertex of the unvisited set with the smallest distance, > 1. Consider all of its unvisited neighbours and calculate the distance to them through the current node. > - If the new distance is less than the currently assigned distance to the neighbour, assign this distance to the neighbour. > 2. Mark the vertex as visited and remove it from the set. > 4. Repeat step 3 for the next unvisited vertex with the smallest distance. *Dijkstra's algorithm* is a [[dynamic programming]] algorithm with [[Greedy Algorithm|greedy]]-like selection of the vertices. It works by considering the shortest path up to any vertex *found so far* and extending these paths to subsequent vertices. If a shorter path is later found to a vertex, its distance is *retroactively updated*. The actual shortest path can be reconstructed by noting the predecessor vertex that led to the updating of the distance to a vertex, then traversing from the destination through the predecessors to the source. Dijkstra's algorithm does not work on graphs with negative weights. ## Time complexity The time complexity of Dijkstra's algorithm depends on the data structures used to represent the graph. If the graph is stored in an adjacency list with a *self-balancing* [[binary search tree]] or [[binary heap]], then the worst-case time complexity is $O((E+V)\log(V))$. The worst-case time complexity is also commonly quoted as $O(E+V\log V)$ which is from using a [[Fibonacci heap]] to represent the graph. In a [[connected graph]], the time complexity can be written as $O(E\log V)$.