Computing path with highest score in a directed graph

Question

I have a directed graph where each node has a score. Starting from a node, I need to find the highest score that can be achieved by following a path. Not all nodes can be final nodes. Also it is possible to revisit a node, but only the first visit counts for the score. How can I compute the highest achievable score?

Answer 1

First you may find a strongly connected components of the graph. Then you may build a condensation of the graph.

Each vertex in condensation may have a score equal to the sum of the scores of vertices in initial graph.

Blue numbers show the score of each vertex in initial graph. Yellow - in graph condensation.

Also mark some of the vertices of the condensation as terminal if they contain a final node. You will also have a mapping of each graph vertex to a vertex in condensation.

The notion of connected component is important because if you find yourself in one vertex of a component you may easily visit all the other vertices of the component to maximise the score. You are free to revisit each vertex any number of times.

Condensation itself is a directed acyclic graph. You can now traverse a condensation graph with depth first search maintaining the function

F_v = 0 - if V does not have reachable termination vertex (bottom-right vertex on the picture below)

F_v = MAX_i(F_childv,i) + score_v - otherwise

Red circles show what vertices in initial graph and condensation considered terminal. Numbers in green show what F-value each vertex in condensation graph has.

The answer to your problem would be F-value of the vertex in condensation that corresponds to a starting vertex in initial graph. Overall time complexity would be O(N + M) wher N is a number of vertices and M - a number of edges in initial graph.