Dijkstra's Shortest-Path Algorithm

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

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.