Dijkstra's algorithm: Difference between revisions

Revision as of 00:34, 6 June 2025

Revision as of 03:05, 11 June 2025

Line 131:

Bounds of the running time of Dijkstra's algorithm on a graph with edges ''{{mvar|E}}'' and vertices ''{{mvar|V}}'' can be expressed as a function of the number of edges, denoted <math>|E|</math>, and the number of vertices, denoted <math>|V|</math>, using [[big-O notation]]. The complexity bound depends mainly on the data structure used to represent the set ''{{mvar|Q}}''. In the following, upper bounds can be simplified because <math>|E|</math> is <math>O(|V|^2)</math> for any simple graph, but that simplification disregards the fact that in some problems, other upper bounds on <math>|E|</math> may hold.

For any data structure for the vertex set ''{{mvar|Q}}'', the running time i sis:{{sfn|Cormen|Leiserson|Rivest|Stein|2001}}

: <math>\Theta(|E| \cdot T_\mathrm{dk} + |V| \cdot T_\mathrm{em}),</math>