Dijkstra's Shortest-Path Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 8: | Line 8: | ||
=Speed Up= | =Speed Up= | ||
The Dijkstra's algorithm can be speed up with the [[Heap#Canonical_Uses_of_a_Heap|use of a heap]] | The Dijkstra's algorithm can be speed up with the [[Heap#Canonical_Uses_of_a_Heap|use of a heap]]. | ||
Revision as of 20:01, 14 October 2021
Internal
Overview
The Problem
The single-source shortest paths is formally defined as follows: given a directed graph G=(V, E) , with n = │V│ and m=│E│, where each edge e has a non-negative length ℓe, and a source vertex s, compute for each v ∈ V the length L(v) of the shortest path s → v.
The assumption that the length is non-negative is important. Dijkstra's shortest-path algorithm does not work correctly in presence of negative length edges.
Speed Up
The Dijkstra's algorithm can be speed up with the use of a heap.