A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS is usually used to find an ordering of the tasks that satisfies all of the precedence constraints, classical DFS algorithm can do it by building the sequence step by step.
Consider now the following variation. Each node $j$ is weighted by a value $w_j$. When we are currently at node $j$, this weight will determine the next node to visit (the one with the higher weight).
Moreover, imagine that each time a node is added to the list, we recompute the weight for the unvisited nodes using a given function (we don't care about the nodes that has already been added to the sequence). Thus at step $t$, the $w_j(t)$ of node $j$ can be different from its weight at step $t+1$.
Questions: Is there a name of this problem ? How to solve it efficiently? (e.g If a node has several successors, one needs to determine the successor with highest weight, so which data structure to use?)
N.B The image is only used for an illustration purpose. The graph is not assumed to be a binary tree.
Edit: the graph is assumed to be connected