Specific Graph and need to more Creative solution

Admin 1
Viewed 209

Directed Graph (|V|=a, |E|=b) is given. each vertexes has specific weight. we want for each vertex (1..a) find a vertex with maximum weight that can be reachable from that vertex.

Update 1: one nice answer is prepare by @Paul in O(b + a log a). but I search for O(a + b) algorithms, if any?

Is there any different efficient or fastest any other ways for doing it?

tree graph data-structures complexity-theory algorithm
2 Answers

Yes, it's possible to modify Tarjan's SCC algorithm to solve this problem in linear time.

Tarjan's algorithm uses two node fields to drive its SCC finding logic: index, which represents the order in which the algorithm discovers the nodes; and lowlink, the minimum index reachable by a sequence of tree arcs followed by a back arc. As part of the same depth-first traversal, we can compute another field, maxweight, which has one of two meanings:

  • For a node not yet included in a finished SCC, it represents the maximum weight reachable by a sequence of tree arcs, optionally followed by a cross arc to another SCC and then any subsequent path.

  • For nodes in a finished SCC, it represents the maximum weight reachable.

The logic for computing maxweight is as follows. If we discover an arc from v to a new node w, then vw is a tree arc, so we compute w.maxweight recursively and update v.maxweight = max(v.maxweight, w.maxweight). If w is on the stack, then we do nothing, because vw is a back arc and not included in the definition of maxweight. Otherwise, vw is a cross arc, and we do the same update that we would have done for a tree arc, just without the recursive call.

When Tarjan's algorithm identifies an SCC, it's because it has a node r with r.lowlink == r.index. Since r is the depth-first search root of this SCC, its value of maxweight is correct for the whole SCC. Instead of recording each node in the SCC, we simply update its maxweight to r.maxweight.

user_21446690

Sort all nodes by weight in decreasing order and create the graph g' with all edges in E reversed (i.e. if there's an edge a -> b in g, there's an edge b -> a in g'). In this graph you can now propagate the maximum-value by simple DFS. Do this iteratively for all nodes and terminate when a maximum-weight has already been assigned.

As pseudocode:

dfs_assign_weight_reachable(node, weight):
    if node.max_weight_reachable >= weight:
        return

    node.max_weight_reachable = weight

    for n = neighbor of node:
        dfs_assign_weight_reachable(n, weight)

g' = g with all edges reversed
nodes = nodes from g' sorted descendingly by weight
assign max_weight_reachable = -inf to each node in nodes

for node in nodes:
    dfs_assign_weight_reachable(node, node.weight)

UPDATE:
The tight bound is O(b + a log a). a log a is caused by the sorting step. And each edge gets visited once during the reversal step and once during the assigning maximum weights, giving the second term in the max-expression.

Acknowledgement:
I'd like to thank @SerialLazer for the time invested in a discussion about the time-complexity of the above algorithm and helping me figure out the correct bound.

user_46686060
Related