Single‐source Shortest paths in directed acyclic graphs - rFronteddu/general_wiki GitHub Wiki

By relaxing the edges of a weighted DAG according to a topological sort of its vertices, we can compute s-p from a single source in O(V+E). Note that no negative edge can exist so s-p are always defined in a DAG.

// O(V+E)
dagShortestPaths (G, w, s)
    topologicalSort (G)
    initializeSingleSource (G,s)
    for u in G.V taken in topological order
        for v in G.Adj[u]
            relax (u, v, w)