Dijkstra's Shortest-Path Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Ovidiu moved page Dijkstra's Algorithm to Dijkstra's Shortest-Path Algorithm without leaving a redirect) |
|||
| Line 2: | Line 2: | ||
* [[Shortest Path in a Graph]] | * [[Shortest Path in a Graph]] | ||
=Overview= | =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 ℓ<sub>e</sub>, and a [[Graph_Concepts#Source_Vertex|source vertex]] s, compute for each v ∈ V the length of the shortest path s → v L(v). | |||
=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 19:46, 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 of the shortest path s → v L(v).
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.