Dijkstra's Shortest-Path Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
* [[Shortest Path in a Graph]] | * [[Shortest Path in a Graph]] | ||
=Overview= | =Overview= | ||
The problem of computing the shortest path in a graph can be solved with bread-first search, but | The problem of computing the shortest path in a graph can be solved with bread-first search, but the [[Breadth-First_Search-based_Shortest_Path_Algorithm|Breadth-First Search-based Shortest Path algorithm]] works in the special case when the [[Graph_Concepts#Edge_Length|length]] of every edge in the graph is 1. | ||
=The Problem= | =The Problem= | ||
Revision as of 20:10, 14 October 2021
External
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/rxrPa/dijkstras-shortest-path-algorithm
- https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/iIzo8/heaps-operations-and-applications
Internal
Overview
The problem of computing the shortest path in a graph can be solved with bread-first search, but the Breadth-First Search-based Shortest Path algorithm works in the special case when the length of every edge in the graph is 1.
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.