This is a blog for cp newbies (like me).

For a long time I think the Dijkstra algorithm (dij) 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);

The graph $$$G = (V(G), E(G))$$$. 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 that are also sufficient:

(1, induction base) $$$\forall s \in S$$$, $$$f(s)$$$ should be correctly initialized.

(2, Extension property) $$$\forall p$$$, for every vertex $$$v$$$ adjacent to the end of $$$p$$$ (p.back()), $$$f(p \cup v) \geq f(p)$$$.

(3, dynamic programming) If path $$$p, q$$$ has the same end (i.e., p.back()==q.back()) and $$$f(p) \geq f(q)$$$, then for every vertex $$$v$$$ adjacent to p.back(), $$$f(p \cup v) \geq f(q \cup v)$$$.

We say that dij works for $$$f$$$ if $$$\forall v \in V(G)$$$, dij correctly computes $$$\min f(\{p|p\,\text{is a S-v path}\})$$$.