// Input: a DAG G s.t.
// for all edge e, e.cost is a real number
//
// At the beginning we assume all backpointers to be NIL
// and for each node n, n.cost to be +infinity
//
// Output: a modified graph G s.t. for all nodes m reachable
// from n in G, n.backpointer points to the previous node
// in a path of minimal cost from n to m
//
// F \in O(|E|+|V|)
F(G,n) {
   L := TopoSort(G)
   n.cost := 0
   for each v in L do
      for each w in AdjSet(v) of cost k do
         if v.cost + k < w.cost then
            w.cost := v.cost + k
            w.backpointer := v
}