Introduction to Shortest Paths

Weighted directed graph (two vertices)

Suppose we are given a weighted directed graph $G = (V, E, w)$ with two special vertices, and we want to find the shortest path from a source vertex $s$ to a target vertex $t$. That is, we want to find the directed path $P$ starting at $s$ and ending at $t$ that minimizes the function

$$w(P) := \underset{u\rightarrow v \epsilon P}{\sum} w(u\rightarrow v).$$ ...