Dijkstra's Shortest-Path Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
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 [[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. Dijkstra's shortest-path algorithm solves a more general problem, where the edges have arbitrary non-negative lengths.
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 ℓe is 1. Dijkstra's shortest-path algorithm solves a more general problem, where the edges have arbitrary non-negative lengths.


=The Problem=
=The Problem=

Revision as of 20:12, 14 October 2021

External

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 ℓe is 1. Dijkstra's shortest-path algorithm solves a more general problem, where the edges have arbitrary non-negative lengths.

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.