- #1
mXSCNT
- 315
- 1
Suppose we have a directed acyclic graph. The nodes are labeled with integers (which may be negative). Imagine that the labels represent payoffs or costs of taking an action associated with each node. In order to perform an action you must perform prerequisite actions indicated by the graph.
The question is whether there is a topological sort on this graph, such that at some point during the ordering, the sum of the labels on all the nodes up to that point becomes positive. This would represent a net profit from taking all actions up to that point.
Example:
[PLAIN]http://img535.imageshack.us/img535/5395/graph1f.png
If we have the topological sort ABCED, the labels on ABCE sum to a positive number (1). So this graph does meet the criteria for being profitable - if you take actions A B C E in that order, you make a profit of 1. Note that if you also took action D, the sum would be -6, so you should stop after E. ABCED is a "profitable topological sort" because it has the prefix ABCE which is profitable. ABCDE is an example of a non-profitable topological sort.
The problem is to find an algorithm to determine whether a directed acyclic graph in general has a profitable topological sort.
The question is whether there is a topological sort on this graph, such that at some point during the ordering, the sum of the labels on all the nodes up to that point becomes positive. This would represent a net profit from taking all actions up to that point.
Example:
[PLAIN]http://img535.imageshack.us/img535/5395/graph1f.png
If we have the topological sort ABCED, the labels on ABCE sum to a positive number (1). So this graph does meet the criteria for being profitable - if you take actions A B C E in that order, you make a profit of 1. Note that if you also took action D, the sum would be -6, so you should stop after E. ABCED is a "profitable topological sort" because it has the prefix ABCE which is profitable. ABCDE is an example of a non-profitable topological sort.
The problem is to find an algorithm to determine whether a directed acyclic graph in general has a profitable topological sort.
Last edited by a moderator: