Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current approach is doing the followings. Add an extra node $S$ (source) and put directed edges to all starting nodes with zero weight. Similarly, add a sink node $T$ and put directed edges from all end nodes to $T$ with zero weight. Now, the problem is to find all maximum weighted paths between $S$ and $T$. Make the edge weights negative, i.e. weight $w$ becomes $-w$. Find the all single-source shortest path from $S$. My question is, if there is any other efficient method to achieve this. The other thing is that, I need to find all maximum weighted paths if there exists more than one such paths. How can I find all maximum weighted paths efficiently?Does maximum flow algorithm help?
maximum weighted path(s) in a DAG
weighted graphs;dag