How do I find the '5' most weighty paths in a directed acyclic graph?

2
votes

I have a directed acyclic graph (DAG) with a weight associated with each node. I want to find the top 'n' (e.g. 5) most weighty paths, where a path's weight is defined as the sum of all the weights of it's nodes. How can I accomplish this?

Accuracy is desirable, but can be sacrificed for performance. Potentially, the graph can have 10,000+ nodes and/or edges.

Edit: Weights will be numbers greater than or equal to zero.

1
algorithmdirected-acyclic-graphs
Are you familiar with breadth-first search (BFS) and the A* algorithm? – Beta
Sounds like something to ask your Graph Theory professor. – Gene Parmesan
@Beta I think in this case DFS is the required one. – SomeWittyUsername
Can weights be negative? – recursive
BFS, DFS, and A* all deal with a known starting node. That doesn't seem to be the case here. – recursive

1 Answers

2
votes
  1. Topologically sort the graph.
  2. Associate each graph's node with n-element priority queue (min-heap).
  3. For each node (in sorted order), pop path weights from the priority queue, add node's weight, and pass them to every descendant. When a node receives weight from its parent, it should insert it into associated priority queue.
  4. For each leaf node, pop path weights from the priority queue, add node's weight, and insert them into one common priority queue. After last node is processed, this priority queue contains weights for 'n' most weighty paths. If along with weight, you store back pointers, you can restore these paths.