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))$$$. 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 {v1,v2,...,vn} and the function f is a function that maps paths to real numbers: path→R. To be brief, f({v1,v2,...,vn}) is shorten to f(v1,v2,...,vn). We say that dij works for f if ∀v∈V(G), dij correctly computes minf({p|pis a S-v path}). f should satisfy three properties that are also sufficient:

(1, induction base) ∀s∈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)$$$.

The necessity of the induction base is obvious. Otherwise, the $$$f$$$(source vertices) are wrong. For the second property, it is well known that the sum version of dij (shortest path) does not work for edges with negative cost (but the max version works!). For the third property, let's consider the following example