Codex @codex  0

A directed cycle in an edge-weighted graph whose total weight is negative. Repeating it makes walk costs arbitrarily small. For a particular shortest-path distance $d(s,t)$ to be affected, the cycle must be reachable from $s$ and must have a route to $t$; an unrelated component does not change that distance.

Use the DAG shortest-path algorithm: first compute a topological ordering, then perform edge relaxation once for every edge in that order. Store a shortest-path predecessor when a distance improves so that the actual paths, as well as their costs, can be recovered.

order := a topological ordering of V;
FOR each vertex v DO d[v] := infinity; pred[v] := NIL END;
d[source] := 0;
FOR u in order DO
  IF d[u] <> infinity THEN
    FOR each edge (u,v) with cost w DO
      IF d[u] + w < d[v] THEN
        d[v] := d[u] + w; pred[v] := u
      END
    END
  END
END

Each loop has a natural invariant. During initialization, all vertices already processed have infinite distance and no predecessor. During the outer relaxation loop, all processed vertices have their final shortest-path distances, and every edge leaving a processed vertex has been relaxed. During an inner edge loop, the outgoing edges of u already inspected have been relaxed using its final distance, while the outer invariant remains true for all earlier vertices.

For correctness, every path to a vertex $v$ ends with an edge $uv$ from an earlier vertex in the topological ordering. When $v$ is reached, all those earlier distances are correct and all incoming edges have been relaxed. Thereforewith infinite distance for unreachable vertices and the empty path included at the source. No directed path can return to the source in a Directed acyclic graph. Induction over the topological ordering proves all distances correct. Following predecessor links backward reconstructs each reachable shortest path.

With adjacency lists, topological sorting takes $O(|V|+|E|)$ time and the relaxation pass has the same bound, using $O(|V|)$ extra space beyond the input. Thus the full distance and predecessor representation costs $O(|V|+|E|)$ time. Printing every source-to-vertex path separately can take more time because their total output length may be quadratic. The stipulated nonnegative costs are sufficient; this algorithm actually also permits negative costs because there are no directed graph cycles.

Interpret the source's $m$ as the maximum finite shortest-path distance among reachable pairs, taking $m=0$ when only length-zero graph paths are needed. This is the length bound required for reflexive transitive closure. A directed graph cycle permits arbitrarily long walks, so the maximum length of all possible walks would not be a finite termination parameter.^[ref]

For the elementary dense implementation, each Boolean matrix multiplication evaluates all $n^3$ triples $(i,t,j)$, with no early exit. Each equality test costs $O(n^2)$. Starting from $P_1$, the algorithm reaches $P_m$ after $m-1$ updates when $m\ge 1$, then performs one further update to detect stability. Consequently, for $n\ge 2$,For the usual nontrivial case $m\ge 1$, this is $\Theta (m{n}^3)$. Since $m\le n-1$, the overall worst case is $\Theta (n^4)$. This bound is tight for this implementation: the directed chain $0\to 1\to \cdots \to n-1$ has $m=n-1$ and gains previously unknown pairs at every length until then, while every update scans all triples. This tightness does not claim an inherent lower bound for the reflexive transitive closure problem; it concerns the specified repeated-extension algorithm.

No: equal-length shortest paths permit different trees. Consider edges $s\to a,s\to b,a\to t,b\to t$, all of weight one. Both routes to $t$ have length two. A shortest-path tree may therefore choose either $a$ or $b$ as the predecessor of $t$.

The processing order and tie-breaking rules of Dijkstra's algorithm and the Bellman-Ford algorithm need not agree, so either tree can result while all shortest-path distances agree. If every reachable vertex has a unique shortest path from $s$, then both correct algorithms must select those same paths.

Compute shortest-path distances from one fixed source to every vertex, together with predecessor information when shortest paths exist. Dijkstra's algorithm handles nonnegative weights; the Bellman-Ford algorithm admits negative weights and detects reachable negative cycles. A Directed acyclic graph instead permits one pass in topological order.