Dijkstra's Shortest-Path Algorithm

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

• Shortest Path in a Graph

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 of computing the shortest path in a graph with arbitrary edge lengths can be theoretically reduced to the problem of computing the shortest path in a graph with edges of length ℓe=1, by replacing an edge with an arbitrary length n with n edges with length 1, and adding extra vertices.

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.