> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/24.-reductions-and-decomposition/24.3-longest-path.md).
# 24.3 Longest Path
## In General
Consider the problem of finding the longest path from a start vertex to every other vertex. The path must be simple (contain no cycles).
It turns out that best known algorithm is exponential (impractically inefficient).
Negating all the edge weights and finding the shortest path leaves us in a tricky situation because then we could have negative cycles and we could go around and around them indefinitely.
## Longest Paths on DAGs
But what if we are dealing with DAGs? In that case, we have no cycles so we can do as suggested above:
1. Form a new copy of the graph, called G', with all edge weights negated (signs flipped).
2. Run DAG shortest paths on G' yielding result X
3. Flip the signs of all values in X.distTo. X.edgeTo is already correct.
Alternatively, we could modify the DAG shortest path algorithm from the previous section to choose the larger distTo when relaxing an edge. While this would make more sense in practice, the benefit of thinking of the first approach is that wree a able to use an existing algorithm as a "[black box](https://en.wikipedia.org/wiki/Black_box)" to solve a new problem. We'll learn more about this kind of problem solving in the next section: [Reductions](https://joshhug.gitbooks.io/hug61b/content/chap214.md).
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/24.-reductions-and-decomposition/24.3-longest-path.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.