Lagmental Vicfred

Dijkstra Finalizes the Smallest Tentative Distance by Vicfred

Last updated: Fri 10 December 2021

tags: mathematics, paths, network flows, matchings

With nonnegative edges, the unsettled vertex of minimum tentative distance already has its true shortest-path distance. I want the notation, the mechanism, and the failure mode visible at the same time.

Start locally

Weighted paths minimize \(\sum_{e\in P}w(e)\), flows use values \(f:E\to\mathbf R_{\ge0}\) with conservation, and matchings enforce degree at most one. Each problem has a dual obstruction.

$$ d(s)=0,\qquad d(v)=\infty\ (v\ne s) $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ d(v)\leftarrow\min\{d(v),d(u)+w(u,v)\} $$

Compute before generalising

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ \left.\begin{aligned}u&=\arg\min_{x\notin S}d(x),\\w(e)&\ge0\end{aligned}\right\}\Longrightarrow d(u)=\delta(s,u) $$

The global view

The formula is reusable precisely because it says which pieces are structural and which belong only to the worked example.

$$ \begin{aligned} \mathsf{D}\;&:\quad d(s)=0,\qquad d(v)=\infty\ (v\ne s),\\[5pt] \mathsf{C}\;&:\quad d(v)\leftarrow\min\{d(v),d(u)+w(u,v)\}. \end{aligned} $$

Edge conditions

Dijkstra requires nonnegative edge weights, while flow capacities must be interpreted on a directed residual network even when the original graph is undirected.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] d(v)\leftarrow\min\{d(v),d(u)+w(u,v)\} \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Thu 11 March 2021. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.