= Solution
The all-to-one <shortest path problem> asks for the minimum length $v_i$ of a <directed path> from every <vertex> $i$ to the root $n$, with $v_n=0$ and $v_i=\infty$ if no such <directed path> exists. Positive <directed edge> lengths allow <directed cycles> to be deleted, so a shortest <directed path>, when one exists, uses at most $n-1$ <directed edges>. Its optimality equations are
$$
v_i=\min_{(i,j)\in A}(c_{ij}+v_j),\qquad i\ne n.
$$
A <Bellman-Ford algorithm> initializes $d_n^{(0)}=0$ and other labels to infinity, then repeats
$$
d_i^{(k)}=\min\left\{d_i^{(k-1)},\min_{(i,j)\in A}(c_{ij}+d_j^{(k-1)})\right\},
$$
keeping the root label zero. Induction on $k$ proves that $d_i^{(k)}$ is the least length among <directed paths> using at most $k$ <directed edges>: either the old best <directed path> remains, or the first <directed edge> is followed by a <directed path> with at most $k-1$ <directed edges>. Thus $n-1$ rounds give the exact distances. An in-place variant repeatedly relaxes $d_i\leftarrow\min(d_i,c_{ij}+d_j)$; each decreased label triggers further incoming-arc relaxations. It terminates when no finite label can improve. The <Bellman inequalities> then telescope along each <directed path> to show the labels are lower bounds on all <directed path> lengths, while every finite label represents a discovered <directed path> and is an upper bound on the optimum. This proves correctness. The method is a <label-correcting shortest-path algorithm>: a processed label can be revised many times. Full scans cost $O(n|A|)$.
Let $d=\min_{i\ne n}c_{in}$ and choose $j$ attaining it. Every <directed path> from a nonroot <vertex> to $n$ has a final <directed edge> costing at least $d$, and all preceding <directed edges> have positive lengths. Therefore every $v_k\ge d$. The direct <directed edge> from $j$ to $n$ has length $d$, so
$$
\boxed{v_j=c_{jn}=d\le v_k\quad(k\ne n).}
$$
If no incoming root <directed edge> exists, all these distances are infinite and there is no finite next <vertex> to settle.
The all-to-one <Dijkstra algorithm> sets the root's label to zero and all others to infinity. Repeatedly choose an unsettled <vertex> $j$ with least finite label, make that label permanent, and relax every incoming <directed edge> $(i,j)$ of an unsettled <vertex>:
$$
d_i\leftarrow\min\{d_i,c_{ij}+d_j\}.
$$
Store the corresponding successor $j$ whenever the label improves. Stop when all <vertices> are settled or every remaining label is infinite. This applies the usual source version to the reversed <graph>; relaxing outgoing original <directed edges> would solve the wrong direction of the problem.
For its correctness, inductively assume every settled distance is exact. Any <directed path> from an unsettled <vertex> to the root must first enter the settled set at some <vertex> $w$, through an <directed edge> $(z,w)$. That <directed edge> has already been relaxed, so $d_z\le c_{zw}+v_w$. The newly selected label $d_j$ is no greater than $d_z$. The <directed path>'s preceding nonnegative lengths therefore make its total length at least $d_j$. On the other hand, $d_j$ itself is the length of a discovered <directed path>. Hence $d_j=v_j$, and it can never need correction. This is a <label-setting shortest-path algorithm>. Straight array selection costs $O(n^2+|A|)$.
For four <vertices> and root 4, the full symbolic execution is as follows. After settling 4, the tentative labels are $(c_{14},c_{24},c_{34},0)$. Select
$$
j\in\operatorname*{argmin}_{i\in\{1,2,3\}}c_{i4},
$$
set $v_j=c_{j4}$, and update the two other labels to $d_i=\min\{c_{i4},c_{ij}+c_{j4}\}$. Select the smaller of those labels at <vertex> $k$, set $v_k=d_k$, then for the last <vertex> $\ell$ set
$$
\boxed{v_\ell=\min\{c_{\ell4},c_{\ell j}+c_{j4},c_{\ell k}+v_k\}.}
$$
The stored successors give the corresponding shortest routes; infinity conventions handle missing <directed edges> and disconnected <vertices>.
\b[The supplied PDF contains no visible network diagram or <directed edge> lengths in the space for this example, and the converted TeX omits the diagram as well. Numerical distances and route choices cannot be determined from the supplied data.] The symbolic run above gives the exact four-node calculation once those lengths are available; no network has been guessed.
Back to article page
