This is a blog for cp newbies (like me).↵
↵
For a long time I think the [Dijkstra algorithm (dij)](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) only has two usages:↵
↵
(1) Calculate the distance between the vertices when the weights of edges are non-negative.↵
↵
(2) (Minimax) Given a path $p = x_1x_2...x_n$, define $f(p) := \max_{i=1}^{n-1}d(x_i, x_{i+1})$. Given source vertex $s$ and target vertex $t$, dij is able to calculate $min \\{f(p)|p\,\text{is a s-t path}\\}$.↵
↵
However, dij works for a function class, not only the sum/max functions. The sum/max functions are only the two most frequently used members of this function class, but the function class is far larger than these two. Once the function $f$ satisfies several mandatory properties, you could use dij. The word "function class" is like an interface in Go/Java and an abstract class in C++:↵
↵
~~~~~↵
struct f{↵
virtual void property1() = 0;↵
virtual void property2() = 0;↵
virtual void property3() = 0;↵
//...↵
};//dijkstra function.↵
dij(f);↵
~~~~~↵
↵
For dij there has to be a non-empty source set $S$. The $S$ needs not to be a singleton, e.g., multi-source dij. A path $p$ is a vector of vertices $\\{v_1, v_2, ..., v_n\\}$ and the function $f$ is a function that maps paths to real numbers: $\text{path} \rightarrow \mathbb{R}$. To be brief, $f(\\{v_1, v_2, ..., v_n\\})$ is shorten to $f(v_1, v_2, ..., v_n)$. $f$ has to satisfy three properties:↵
↵
(1, induction base) $\forall s \in S$, $f(s)$ should be correctly initialized.↵
(2, Extension property) $\forall p$, for every vertex $v$, that is neighbor to the last vertex of $p$ (`p.back()`), $f(p \cup v) \geq f(p)$.↵
↵
For a long time I think the [Dijkstra algorithm (dij)](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) only has two usages:↵
↵
(1) Calculate the distance between the vertices when the weights of edges are non-negative.↵
↵
(2) (Minimax) Given a path $p = x_1x_2...x_n$, define $f(p) := \max_{i=1}^{n-1}d(x_i, x_{i+1})$. Given source vertex $s$ and target vertex $t$, dij is able to calculate $min \\{f(p)|p\,\text{is a s-t path}\\}$.↵
↵
However, dij works for a function class, not only the sum/max functions. The sum/max functions are only the two most frequently used members of this function class, but the function class is far larger than these two. Once the function $f$ satisfies several mandatory properties, you could use dij. The word "function class" is like an interface in Go/Java and an abstract class in C++:↵
↵
~~~~~↵
struct f{↵
virtual void property1() = 0;↵
virtual void property2() = 0;↵
virtual void property3() = 0;↵
//...↵
};//dijkstra function.↵
dij(f);↵
~~~~~↵
↵
For dij there has to be a non-empty source set $S$. The $S$ needs not to be a singleton, e.g., multi-source dij. A path $p$ is a vector of vertices $\\{v_1, v_2, ..., v_n\\}$ and the function $f$ is a function that maps paths to real numbers: $\text{path} \rightarrow \mathbb{R}$. To be brief, $f(\\{v_1, v_2, ..., v_n\\})$ is shorten to $f(v_1, v_2, ..., v_n)$. $f$ has to satisfy three properties:↵
↵
(1, induction base) $\forall s \in S$, $f(s)$ should be correctly initialized.↵
(2, Extension property) $\forall p$, for every vertex $v$, that is neighbor to the last vertex of $p$ (`p.back()`), $f(p \cup v) \geq f(p)$.↵
