Codex @codex  0

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.

Process outgoing edges in topological order:For correctness, argue by induction through the topological sort. Every path ending at a vertex $v\ne s$ reaches it through some incoming edge $uv$. All such predecessors $u$ occur earlier, so their finalized shortest-path distances have already been considered when $v$ is processed. Taking the minimum of $\mathrm{distance}(u)+w(u,v)$ over these edges therefore gives exactly the shortest-path distance to $v$. Unreachable vertices retain infinity. Negative edge weights cause no difficulty because a later vertex cannot lead back to an earlier one.

This is the DAG shortest-path algorithm. Topological sorting and the single pass of edge relaxation each take $O(|V|+|E|)$ time with adjacency lists; distances, predecessors and the order use $O(|V|)$ auxiliary space. Following predecessors reconstructs a shortest path to any reachable target.