Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to what you describe:
In your case we could implement it similar to the following (transcribed mostly from CLRS 24.2) assuming input is an adjacency list:
0. Max-Weight-Paths(Graph G(E, V)):
1. add Super-Source S, and Super-Sink T // takes O(V + E)
2. negate all edge weights // takes O(V + E)
3. topological sort G.V // takes O(V + E)
4. for each vertex u in sorted order:
5. for each vertex v in G.adj[u]:
6. Relax(u, v) // 4-6 takes O(V + E)
Now for returning all max weight paths we can simply modify the relaxation step (6) a little bit. Instead of only containing a back pointer to one parent, we can maintain a linked list of back pointers to all parents of equal total distance like so:
0. Relax(Vertex u, Vertex v):
1. if distance(v) > distance(u) + w(u, v):
2. distance(v) = distance(u) + w(u, v)
3. parents(v) = {u}
4. elif distance(v) == distance(u) + w(u, v):
5. add u to parents(v)
Assuming parents(v)
is maintained as a list, the Relax
step still takes $O(1)$.
Then in the end you can return all max weight paths by starting at the sink T
and traversing back up through parents(T)
an so on. This traversal will return a DAG itself if multiple max weight paths exist. So just be smart about the traversal and the whole thing should take $O(V + E)$.
Edit, when I say be smart about the returning traversal, keep in mind a bad case scenario, something like this where all edge weights are equal:

There would technically be $6^2$ max weight paths, you could expand this example to get graphs with very large amounts of max weight paths due to combinatorics. So it might be more useful to return the DAG of max-weight paths rather than each individual. Although if you must return individual paths then you might be out of luck, because there are a lot of possibilities.