Directed Shortest Path Problems
Why
1Definition
Suppose we want to find the shortest path on a weighted graph from a given starting vertex to a given terminal vertex.
Let $((V, E), w: E \to \R )$ be a weighted directed graph. Let $v$ be a source and $w$ be a sink. Let $\mathcal{X} $ denote the set of (directed) paths from $v$ to $w$. Let $f: \mathcal{X} \to \R $ be so that if $x \in X$ is a path from $v$ to $w$, then $f(x)$ is the weight of the path. In other words, $f(x)$ is the sum of weights on the edges. Then we call the problem $(\mathcal{X} , f)$ a directed shortest path problem.