Dijkstra's Shortest-Path Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 5: Line 5:
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 ℓ<sub>e</sub>, and a [[Graph_Concepts#Source_Vertex|source vertex]] s, compute for each v ∈ V the [[Graph_Concepts#Path_Length|length]] L(v) of the shortest path s → v.
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 ℓ<sub>e</sub>, and a [[Graph_Concepts#Source_Vertex|source vertex]] s, compute for each v ∈ V the [[Graph_Concepts#Path_Length|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 paths.
The assumption that the length is non-negative is important. Dijkstra's shortest-path algorithm does not work correctly in presence of [[Graph_Concepts#Negative_Length_Edge|negative length edges]].


=Speed Up=
=Speed Up=
The Dijkstra's algorithm can be speed up with the [[Heap#Canonical_Uses_of_a_Heap|use of a heap]]. <font color=darkgray>TODO: https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications</font>.
The Dijkstra's algorithm can be speed up with the [[Heap#Canonical_Uses_of_a_Heap|use of a heap]]. <font color=darkgray>TODO: https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications</font>.

Revision as of 20:00, 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. TODO: https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications.