kratos99's blog

Need help with a graph therory problem
By kratos99, history, 5 years ago, In English

I have recently learnt the technique to find strongly connected components in directed graph so i was trying this problem but i can't find solution.

Can you help me solve this problem?

Thanks in advance.

Happy Coding :)

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know how to solve this problem but I think you can use DP or DFS.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

This is how I did it

First of all find all the strongly connected components.The path that you will follow is would be like u -> v -> .... -> y where u is SCC of start node and y is SCC of end node, in between you would come accross a number (>=0) of other SCC's as well. The point is if you will go at node h then you will go to all vertices of h's SCC to maximize the value.

So path has been stated by me in terms of SCC. Note that after getting the SCC's if we consider each SCC as a node of some new graph then this new graph would be a directed acyclic graph where value of a SCC node is sum of values of all the nodes in it,

The problem now reduces to finding a path from start node's SCC to end node's SCC with maximum value. To do this we will only consider SCC nodes which are in subgraph of the new graph whose root is start node's SCC. Once we have this subgraph the problem reduces to find maximum value in going from root to end node's SCC.

This can now be done by dynamic programming by traversing SCC nodes in the topological sorting manner.

Please pardon my poor english. I feel I might not be clear beacuse of the long solution. Feel free to reach out for any explainations.

Hope it helps :)

→ Reply