The current solution suggests to start from the marked vertices and go up the predecessor tree to mark all these nodes with -infinity. But these nodes are not necessarily reachable from these mark nodes, i.e. the direction in which we traverse is wrong. We should simply run a DFS on the marked nodes to see all the ones that are reachable from them.
walkccc
commented
2 years ago
The current solution suggests to start from the marked vertices and go up the predecessor tree to mark all these nodes with -infinity. But these nodes are not necessarily reachable from these mark nodes, i.e. the direction in which we traverse is wrong. We should simply run a DFS on the marked nodes to see all the ones that are reachable from them.