Dijkstra's Shortest-Path Algorithm

From NovaOrdis Knowledge Base
Revision as of 20:10, 14 October 2021 by Ovidiu (talk | contribs) (→‎Overview)
Jump to navigation Jump to search

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 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.