Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits minimum number of nodes (shortest path).

I have created a DAG from the directed graph and performed a topological sort on it. Now I can easily find paths that passes maximum number of components by traversing the DAG, but I have problem finding the shortest one of them. Of course you can brute-force over all of these paths and find the shortest one of them but this is not acceptable because my graph has 1000 nodes.