Dijkstra's algorithm: Difference between revisions
no edit summary
No edit summary |
|||
Line 1:
{{task|Classic CS problems}}
{{clarified-review}}
<br>
'''Dijkstra's algorithm''', conceived by Dutch computer scientist [[wp:Edsger Dijkstra|Edsger Dijkstra]] in 1956 and published in 1959, is a [[wp:graph search algorithm|graph search algorithm]] that solves the single-source [[wp:shortest path problem|shortest path problem]] for a [[wp:graph (mathematics)|graph]] with nonnegative [[wp:edge (graph theory)|edge]] path costs, producing a [[wp:shortest path tree|shortest path tree]]. This algorithm is often used in [[wp:routing|routing]] and as a subroutine in other graph algorithms.
Line 715:
The main difference with the time complexity analysis for the previous algorithm is that here, we may add a vertex to the priority queue more than once. However, it is still true that the inner loop executes at most once for each directed edge. This is because in the outer loop, we added a check to ignore vertexes that we've already processed, so we will still only proceed down to the processing the edges at most once for each vertex. Therefore, the number of times that push is done on the priority queue (which happens at most once per iteration of the inner loop) is bounded by E, and the size of the priority queue is also bounded by E.
The number of times
|