Single-Source Shortest Paths

Analysis and Design of Algorithms

Jesus A. Gonzalez

July 17, 2019

Problem of Finding the Shortest Path

Problem of Finding the Shortest Path

Problem of Finding the Shortest Path

Problem of Finding the Shortest Path

\[w(p) = \sum_{i = 1}^k w(v_{i-1}, v_i)\]

Problem of Finding the Shortest Path

\(\delta (u, v) = \begin{cases} min\lbrace w(p): u \overset{p}{\longrightarrow} v\rbrace &\mbox{if there is a path from u to v}\\ \infty &\mbox{any other way}\\ \end{cases}\)

Modeling the Problem

Variants of the Problem

Variants of the Problem

Variants of the Problem

Optimal Substructure of a Shortest Path

Optimal Substructure of a Shortest Path

Optimal Substructure of a Shortest Path - Proof to lemma 24.1

Representation of the Shortest paths

Representation of the Shortest paths

Relaxation Technique

Relaxation Technique

Relaxation Technique

Relaxation Technique

Relaxation Technique

Negative Cycles

Properties of Shortest Paths and Relaxation

Properties of Shortest Paths and Relaxation

Properties of Shortest Paths and Relaxation

Bellman-Ford Algorithm

Bellman-Ford Algorithm

Bellman-Ford Algorithm

Bellman-Ford Algorithm

Bellman-Ford Algorithm

Bellman-Ford Algorithm