Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra's Algorithm - Coggle Diagram
Dijkstra's Algorithm
We consider the single-source shortest-paths problem: for a given vertex called the source in a weighted connected graph, find shortest paths to all its other vertices.
It is important to stress that we are not interested here in a single shortest path that starts at the source and visits all the other vertices.
-
-
In general, before its ith iteration commences, the algorithm has already identified the shortest paths to i − 1 other vertices nearest to the source.
These vertices, the source, and the edges of the shortest paths leading to them from the source form a subtree Ti of the given graph.
Since all the edge weights are nonnegative, the next vertex nearest to the source can be found among the vertices adjacent to the vertices of
Ti.
The set of vertices adjacent to the vertices in Ti can be referred to as “fringe vertices” they are the candidates from which Dijkstra’s algorithm selects the next vertex nearest to the source.
Actually, all the other vertices can be treated as
fringe vertices connected to tree vertices by edges of infinitely large weights.
To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u, the sum of the distance to the nearest tree vertex v (given by the weight of the edge (v, u)) and the length dv of the shortest path from the source to v (previously
determined by the algorithm) and then selects the vertex with the smallest such sum.
The fact that it suffices to compare the lengths of such special paths is the central insight of Dijkstra’s algorithm.
To facilitate the algorithm’s operations, we label each vertex with two labels. The numeric label d indicates the length of the shortest path from the source to this vertex found by the algorithm so far; when a vertex is added to the tree, d indicates the length of the shortest path from the source to that vertex.
The other label indicates the name of the next-to-last vertex on such a path, i.e., the parent of the vertex in the tree being constructed. (It can be left unspecified for the source s and vertices that are adjacent to none of the current tree vertices.)
With such labeling, finding the next nearest vertex u∗ becomes a simple task of finding a fringe vertex with the smallest d value. Ties can be broken arbitrarily.
After we have identified a vertex u∗ to be added to the tree, we need to perform
two operations:
-
The time efficiency of Dijkstra’s algorithm depends on the data structures used for implementing the priority queue and for representing an input graph itself.
It is in Θ(|V|^2) for graphs represented by their weight matrix and the priority queue implemented as an unordered array.
For graphs represented by their adjacency lists and the priority queue implemented as a min-heap, it is in O(|E| log |V|).