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}\}$$$.

I want to say that dij works for a function class, not only the sum/max functions. Once the function $$$f$$$ satisfies several mandatory properties, you could use dij. You could view more formal statements in the paragraphs below.

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}$$$.