Dijkstra’s algorithm solves the single-source shortest-paths problem on a directed weighted graph G = (V, E),
where all the edges are non-negative (i.e., w(u, v) ≥ 0 for each edge (u, v) Є E).
Analysis
The complexity of this algorithm is fully dependent on the implementation of Extract-Min function. If extract min function is implemented using linear search, the complexity of this algorithm is O(V2 + E).
In this algorithm, if we use min-heap on which Extract-Min() function works to return the node from Q with the smallest key, the complexity of this algorithm can be reduced further.
Example
Let us consider vertex 1 and 9 as the start and destination vertex respectively. Initially, all the vertices except the start vertex are marked by ∞ and the start vertex is marked by 0.
Hence, the minimum
distance of vertex 9 from vertex 1 is 20. And the path is 1→ 3→ 7→ 8→ 6→ 9
0 Comments