UVa 10000

From Algorithmist
Jump to navigation Jump to search

10000 - Longest Paths[edit]

Summary[edit]

Finding the longest path in a general graph is NP-Complete. However, since the graph we are given is a directed acyclic graph with a small N, we can use a relatively naive exhaustive search algorithm to solve this. Alternatively, we can use dynamic programming to solve this.

Exhaustive Search Explanation[edit]

We can use exhaustive search on the graph, since it's a directed acyclic graph. Recursion should suffice.

Exhaustive Search Optimizations[edit]

Store the best path from the start node to the all the nodes using linear space. Only branch if the current path is longer than the longest path to current node.

Dynamic Programming Explanation[edit]

Since the graph is acyclic, there is a topological ordering. Thus, we can topological sort the graph, and use dynamic programming on the following recurrence:

where p(i,j) is is defined as 1 if there is a path from node i to node j, and 0 otherwise.

We can topological sort in time, and the dynamic programming portion can be implemented trivially in time, or non-trivially in time.

Notes[edit]

  • The input was increased, so optimization may or may not be necessary.

Gotchas[edit]

Print a new line after each test case.

Input[edit]

2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0

Output[edit]

Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.

Solutions[edit]

C++: http://codealltheproblems.blogspot.com/2015/06/uva-10000-longest-paths.html