# UVa 10000

## Contents

## 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