> 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/22.-shortest-paths/22.1-introduction.md).

# 22.1 Introduction

## Shortest Paths <a href="#shortest-paths" id="shortest-paths"></a>

### Recalls <a href="#recalls" id="recalls"></a>

So far, we have methods to do the following

* find a path from a given vertex, `s`, to every reachable vertex in the graph.
* find a **shortest** path from a given vertex, `s`, to every reachable vertex in the graph. (...or do we?)

Before we answer the mysterious question posed below, let's further recall the two types of searches we could use to do the above two things: BFS or DFS.

Are both going to always be correct? Yes. Does one give better results? BFS finds you the **shortest** paths whereas DFS does not. Is one more efficient than the other, runtime-wise? No. Is one more efficient than the other, space-wise?

* DFS is worse for spindly graphs. Imagine a graph with 10000 nodes all spindly. We'll end up making 10000 recursive calls, which is bad for space.
* BFS is worse for "bushy" graphs, because our queue gets used a lot.

### Answering the mysterious question <a href="#answering-the-mysterious-question" id="answering-the-mysterious-question"></a>

Did we develop an algorithm to find the **shortest** path from a given vertex to every other reachable vertex? Well, kind of. We developed an algorithm that works well on graphs with no edge labels. Here's what we did: we developed an algorithm that finds us the shortest (**where shortest means the fewest number of edges**) paths from a given source vertex.

But that's not always the correct definition of shortest. Sometimes, our graph edges might have 'weights', and A-B is considered farther than A-C if the A-B edge has weight, say, 5 and the A-C edge only has weight, say, 3.

That is why we need a different algorithm for finding the shortest path when we have the edge weights in the graph.


---

# 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/22.-shortest-paths/22.1-introduction.md?ask=<question>&goal=<endgoal>
```

`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.