 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 areA Bellman-Ford algorithm initializes $d_n^{(0)}=0$ and other labels to infinity, then repeatskeeping 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$, soIf 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: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)$. Selectset $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$ setThe stored successors give the corresponding shortest routes; infinity conventions handle missing directed edges and disconnected vertices.

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.