Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra's Algorithm, a - Coggle Diagram
Dijkstra's Algorithm
-
Definition
It's a algorithm for the single-source shortest-paths problem. Dijkstra's algorithm finds the shortest paths to a graph's vertices in order of their distance from a given source. This algorithm is applicable to undirected and directed graphs with nonnegative weights only.
Steps
First, find the closest node to v (itself)
On the i-th step:
-
Since there are no negative weights, the next closest one is adjacent to one of the i−1 closest nodes to v
After chosing the i−th closest node (w), updates the possible shortest paths to yet unchosen nodes (u) if dw + weight(w, u) < du
-
Time efficiency
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|²) 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|). A still better upper bound can be achieved for Dijkstra's algorithm (for Prim's algorithm also) if the priority queue is implemented using a sophisticated data structure called the Fibonacci heap. However, its complexity and a considerable
overhead make such an improvement primarily of theoretical value.
It's a greedy algorithm. That means it constructs a solution through a sequence of steps, each expanding a partially constructed solution.
On each step, the choice made must be:
-> Feasible: satisfies the problem’s constraints
-> Locally optimal: best feasible local choice
-> Irrevocable: cannot be changed later
-