1 of 72

1

WARNING, THESE SLIDES HAVE NOT YET BEEN UPDATED FOR FALL 2026

2 of 72

2

CS61B, Spring 2026 @ UC Berkeley

Josh Hug and Manuel Sabin

Directed Acyclic Graphs

Lecture 25 (Graphs 5)

3 of 72

Quick Note: Teaching in the Future is Amazingly Fun

3

4 of 72

Self-report on the Project 4B Process

4

5 of 72

Self-report on the Project 4B Process

5

6 of 72

Goals of Today

Today, to practice our problem solving skills, we’ll work through some very challenging A-level problems using the tools we’ve already learned about.

Will focus on graphs, but the ideas today are more general.

6

7 of 72

Graph Problems So Far

7

Problem	Problem Description	Solution	Efficiency
paths	Find a path from s to every reachable vertex.	DepthFirstPaths.java Demo	O(V+E) time Θ(V) space
shortest paths	Find the shortest path from s to every reachable vertex.	BreadthFirstPaths.java Demo	O(V+E) time Θ(V) space
shortest weighted paths	Find the shortest path, considering weights, from s to every reachable vertex.	DijkstrasSP.java Demo	O(E log V) time Θ(V) space
shortest weighted path (extra topic, out of scope)	Find the shortest path, consider weights, from s to some target vertex (extra topic, out of scope)	A*: Same as Dijkstra’s but with h(v, goal) added to priority of each vertex. Demo	Time depends on heuristic. Θ(V) space

8 of 72

Graph Problems So Far

8

Problem	Problem Description	Solution	Efficiency
minimum spanning tree	Find a minimum spanning tree.	LazyPrimMST.java Demo	O(???) time Θ(???) space
minimum spanning tree	Find a minimum spanning tree.	PrimMST.java Demo	O(E log V) time Θ(V) space
minimum spanning tree	Find a minimum spanning tree.	KruskalMST.java Demo	O(E log E) time Θ(E) space

9 of 72

Topological Sorting

Lecture 25, CS61B, Spring 2026

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

Definition
Reduction to 3SAT (Optional CS170 Preview)

9

10 of 72

Topological Sort

Suppose we have tasks A through H, where an arrow from v to w indicates that v must happen before w.

What algorithm do we use to find a valid ordering for these tasks?
Valid orderings include: [A, C, B, D, F, E, H, G], [C, A, D, F, B, E, G, H], …

10

B

C

D

E

F

G

H

A

11 of 72

Solution (Spoiler Alert)

Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.

Record DFS postorder in a list.
Topological ordering is given by the reverse of that list (reverse postorder).

11

B

C

D

E

F

G

H

A

12 of 72

Topological Sort (Demo 1/2)

12

A

B

C

D

E

F

G

H

Postorder: []

Call stack: A

*

A

B

C

D

E

F

G

H

Postorder: []

Call stack: A→B

*

A

B

C

D

E

F

G

H

Postorder: []

Call stack: A→B→E

*

A

B

C

D

E

F

G

H

Postorder: [H]

Call stack: A→B→E→H

*

A

B

C

D

E

F

G

H

Postorder: [H, E]

Call stack: A→B→E

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B]

Call stack: A→B

*

A

B

C

D

E

F

G

H

*

Postorder: [H, E, B]

Call stack: A

A

B

C

D

E

F

G

H

*

Postorder: [H, E, B, D]

Call stack: A→D

13 of 72

Topological Sort (Demo 2/2)

13

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D]

Call stack: A→D

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D, A]

Call stack: A

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D, A]

Call stack: C

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D, A]

Call stack: C→F

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D, A, G]

Call stack: C→F→G

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D, A, G, F]

Call stack: C→F

*

A

B

C

D

E

F

G

H

Postorder: [H, E, B, D, A, G, F, C]

Call stack: C

14 of 72

Solution (Spoiler Alert)

Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.

Record DFS postorder in a list: [H, E, B, D, A, G, F, C]
Topological ordering is given by the reverse of that list (reverse postorder):

[C, F, G, A, D, B, E, H]

14

B

C

D

E

F

G

H

A

15 of 72

Topological Sort

The reason it’s called topological sort: Can think of this process as sorting our nodes so they appear in an order consistent with edges, e.g. [C, F, G, A, D, B, E, H]

When nodes are sorted in diagram, arrows all point rightwards.

15

A

B

C

D

E

F

G

H

A

B

C

D

E

F

G

H

16 of 72

Depth First Search

Be aware, that when people say “Depth First Search”, they sometimes mean with restarts, and they sometimes mean without.

For example, when we did DepthFirstPaths for reachability, we did not restart.

For Topological Sort, we restarted from every vertex with indegree 0.

16

17 of 72

Question (Extra Slide)

What is the runtime to find all vertices of indegree 0?

17

18 of 72

Question (Extra Slide)

What is the runtime to find all vertices of indegree 0?

Interesting thing I did not tell you: You don’t have to.

Another better topological sort algorithm:

Run DFS from an arbitrary vertex.
If not all marked, pick an unmarked vertex and do it again.
Repeat until done.

18

19 of 72

Test Your Understanding: yellkey.com/member

Give a topological ordering for the graph below (a.k.a. topological sort).

Give your answer as a comma separated list, e.g. A, B, C, D, E, F

19

B

D

C

E

F

A

s

4

1

2

6

1

3

20 of 72

Test Your Understanding

Give a topological ordering for the graph below (a.k.a. topological sort)

A, D, B, C, E, F (one way to find topo sort: DFS postorder is FECBDA)

20

B

D

C

E

F

A

s

4

1

2

6

1

3

B

D

C

E

F

A

s

4

2

6

1

3

2

Recall that we can think of topological sort as an ordering of “tasks”.

21 of 72

Directed Acyclic Graphs

A topological sort only exists if the graph is a directed acyclic graph (DAG).

For the graph below, there is NO possible ordering where all arrows are respected.

DAGs appear in many real world applications, and there are many graph algorithms that only work on DAGs.

21

A

B

C

D

E

F

G

H

22 of 72

Graph Problems

22

Problem	Problem Description	Solution	Efficiency
topological sort	Find an ordering of vertices that respects edges of our DAG.	Demo Topological.java	O(V+E) time Θ(V) space

23 of 72

Shortest Paths on DAGs

Lecture 25, CS61B, Spring 2026

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

Definition
Reduction to 3SAT (Optional CS170 Preview)

23

24 of 72

Shortest Paths Warmup

What is the shortest paths tree for the graph below, using s as the source? In what order will Dijkstra’s algorithm visit the vertices?

24

Graph from Algorithms, by Vazirani/Papadimitriou

B

D

C

E

F

A

s

4

1

2

6

1

3

25 of 72

Shortest Paths Warmup

What is the shortest paths tree for the graph below, using s as the source? In what order will Dijkstra’s algorithm visit the vertices?

A, B, D, E, F, C

25

B

D

C

E

F

A

s

4

1

2

1

3

1

2

5

7

6

26 of 72

Shortest Paths Warmup

If we allow negative edges, Dijkstra’s algorithm can fail.

For example, below we see Dijkstra’s just before vertex C is visited.

26

B

D

C

E

F

A

s

25

1

6

1

-20

1

2

7

3

27 of 72

Shortest Paths Warmup

If we allow negative edges, Dijkstra’s algorithm can fail.

For example, below we see Dijkstra’s just before vertex C is visited.
Relaxation on E succeeds, but distance to F will never be updated.

27

B

D

C

E

F

A

s

25

1

6

1

-20

1

2

7

3

-13

28 of 72

Shortest Paths Warmup

If we allow negative edges, Dijkstra’s algorithm can fail.

For example, below we see Dijkstra’s just before vertex C is visited.
Relaxation on E succeeds, but distance to F will never be updated.

28

B

D

C

E

F

A

s

25

1

6

1

-20

1

7

3

-13

distTo is wrong!

29 of 72

Challenge

Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.

Hint: You should still use the “relax” operation as a basic building block.

29

B

D

C

E

F

A

s

25

1

6

1

-20

1

∞

30 of 72

Challenge

Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.

Hint: You should still use the “relax” operation as a basic building block.

One simple idea: Visit vertices in topological order.

On each visit, relax all outgoing edges.
Each vertex is visited only when all possible info about it has been used!

30

B

D

C

E

F

A

s

25

1

6

1

-20

1

∞

31 of 72

The DAG SPT Algorithm: Relax in Topological Order

First: We have to find a topological order, e.g. ADBCEF. Runtime is O(V + E).

31

B

D

C

E

F

A

s

25

1

6

1

-20

1

B

D

C

E

F

A

s

25

1

6

1

-20

1

∞

32 of 72

The DAG SPT Algorithm: Relax in Topological Order

Second: We have to visit all the vertices in topological order, relaxing all edges as we go. Let’s see a demo.

32

B

D

C

E

F

A

s

1

6

1

-20

1

25

33 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

33

distTo edgeTo

A 0 -

B ∞ -

C ∞ -

D ∞ -

E ∞ -

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

Fringe: [A, D, B, C, E, F]

0

∞

25

34 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

34

distTo edgeTo

A 0 -

B ∞ -

C ∞ -

D ∞ -

E ∞ -

F ∞ -

B

D

C

D

F

A

s

1

6

1

-20

1

0

∞

Fringe: [A, D, B, C, E, F]

25

35 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

35

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E ∞ -

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

Fringe: [A, D, B, C, E, F]

25

36 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

36

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E ∞ -

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

Fringe: [A, D, B, C, E, F]

25

37 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

37

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

2

Fringe: [A, D, B, C, E, F]

25

38 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

38

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

2

Fringe: [A, D, B, C, E, F]

25

39 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

39

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

7

2

Fringe: [A, D, B, C, E, F]

25

40 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

40

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

7

2

Fringe: [A, D, B, C, E, F]

25

41 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

41

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

7

2

-13

8

Fringe: [A, D, B, C, E, F]

25

42 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

42

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

0

1

7

-13

8

Fringe: [A, D, B, C, E, F]

25

43 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

43

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F -12 E

B

D

C

E

F

A

s

1

6

1

-20

1

0

∞

1

7

-13

-12

Fringe: [A, D, B, C, E, F]

25

44 of 72

DAG SPT Algorithm

Visit vertices in topological order.

When we visit a vertex: relax all of its going edges.

44

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F -12 E

B

D

C

E

F

A

s

1

6

1

-20

1

0

1

7

-13

-12

Fringe: [A, D, B, C, E, F]

25

45 of 72

The DAG SPT Algorithm: Relax in Topological Order

Second: We have to visit all the vertices in topological order, relaxing all edges as we go.

Runtime for step 2 is also O(V + E).

Occasional question asked by students: why isn’t it O(V*E)? We’re relaxing all edges from each vertex.

Keep in mind that E is the total number of edges in the entire graph, not the number of edges per vertex.�Example: for the graph below, E = 8.

45

B

D

C

E

F

A

s

1

6

1

-20

1

46 of 72

Graph Problems

Note: The DAG shortest paths solution uses the topological sort solution as a subroutine.

46

Problem	Problem Description	Solution	Efficiency
topological sort	Find an ordering of vertices that respects edges of our DAG.	Demo Code: Topological.java	O(V+E) time Θ(V) space
DAG shortest paths	Find a shortest paths tree on a DAG.	Demo Code: AcyclicSP.java	O(V+E) time Θ(V) space

47 of 72

What If It’s Not a DAG?

The DAG algorithm only works on graphs that contain no cycles.

If a graph has negative edges, and includes some cycles, can’t use DAG algorithm.
Finding a fast algorithm on such graphs was an open problem for 40 years, solved in 2022 by Bernstein, Nanongkai and Wulff-Nilsen.

Read more here: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/

47

48 of 72

Longest Paths

Lecture 25, CS61B, Spring 2026

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

Definition
Reduction to 3SAT (Optional CS170 Preview)

48

49 of 72

The Longest Paths Problem

Consider the problem of finding the longest path tree (LPT) from s to every other vertex. The path must be simple (no cycles!).

49

B

C

D

E

F

G

A

s

5

2

1

15

3

2

11

5

1

4

1

50 of 72

The Longest Paths Problem

Consider the problem of finding the longest path tree (LPT) from s to every other vertex. The path must be simple (no cycles!).

Some surprising facts:

Best known algorithm is exponential (extremely bad).
Perhaps the most important unsolved problem in mathematics.

50

Two potentially interesting exercises after lecture:

Find an example where the obvious algorithm (Dijkstra’s but pick the biggest edge first) fails.
Figure out: Is the longest path to every other vertex always a tree (i.e. does an LPT exist for all graphs)?

B

C

D

E

F

G

A

s

5

2

1

15

3

2

11

5

1

4

1

2

13

7

15

22

20

51 of 72

The Longest Paths Problem on DAGs

Difficult challenge for you.

Solve the LPT problem on a directed acyclic graph.
Algorithm must be O(E + V) runtime.

51

B

D

C

E

F

A

s

4

1

2

6

1

3

6

2

12

14

13

0

52 of 72

The Longest Paths Problem on DAGs

DAG LPT solution for graph G:

Form a new copy of the graph G’ with signs of all edge weights flipped.
Run DAGSPT on G’ yielding result X.
Flip signs of all values in X.distTo. X.edgeTo is already correct.

52

B

D

C

E

F

A

s

-4

-1

-2

-6

-1

-3

-6

-2

-12

-14

-13

0

53 of 72

The Longest Paths Problem on DAGs

DAG LPT solution for graph G:

Form a new copy of the graph G’ with signs of all edge weights flipped.
Run DAGSPT on G’ yielding result X.
Flip signs of all values in X.distTo. X.edgeTo is already correct.

53

B

D

C

E

F

A

s

6

2

12

14

13

0

54 of 72

A Note on “Mathematical Maturity”

If you have a very high degree of so-called “mathematical maturity”, this algorithm should seem plainly correct.

There’s no real need to prove anything or show demos.

We know DAG SPT works on graphs with negative edge weights.
We also know that -(-a + -b + -c + -d) = a + b + c + d.

Part of what you’re learning in your intense technical education here at Berkeley is mathematical maturity. Hasn’t been a major focus in 61B, but will be in other courses like EECS 16A, EECS 16B, CS 126, CS 127, CS 70, CS 170, Math 110, ...

54

55 of 72

Highly Recommended Exercise For Later

Play around with the longest paths problem and convince yourself that it is actually very hard.

Try to develop an intuition for why it is hard. Even better if you try to put it into english.
Try searching the internet for “why longest paths hard” or similar if you’re having trouble really pinning down what’s so hard about it.

55

56 of 72

Graph Problems

56

Problem	Problem Description	Solution	Efficiency
topological sort	Find an ordering of vertices that respects edges of our DAG.	Demo Code: Topological.java	O(V+E) time Θ(V) space
DAG shortest paths	Find a shortest paths tree on a DAG.	Demo Code: AcyclicSP.java	O(V+E) time Θ(V) space
longest paths	Find a longest paths tree on a graph.	No known efficient solution.	O(???) time O(???) space
DAG longest paths	Find a longest paths tree on a DAG.	Flip signs, run DAG SPT, flip signs again.	O(V+E) time Θ(V) space

57 of 72

Reductions: Definition

Lecture 25, CS61B, Spring 2026

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

Definition
Reduction to 3SAT (Optional CS170 Preview)

57

58 of 72

DAG Longest Paths

The problem solving we just used probably felt a little different than usual:

Given a graph G, we created a new graph G’ and fed it to a related (but different) algorithm, and then interpreted the result.

58

G

DAG-LPT

Preprocess

DAG-SPT

G’

SPT of G’

Postprocess

LPT of G

59 of 72

Reduction

This process is known as reduction.

Since DAG-SPT can be used to solve DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

59

G

DAG-LPT

Preprocess

DAG-SPT

G’

SPT of G’

Postprocess

LPT of G

60 of 72

Reduction Analogy

This process is known as reduction.

Since DAG-SPT can be used to solve DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

As a real-world analog, suppose we want to climb a hill. There are many ways to do this:

“Climbing a hill” reduces to “riding a ski lift.”
“Climbing a hill” reduces to “being shot out of a cannon.”
“Climbing a hill” reduces to “riding a bike up the hill.”

60

61 of 72

Reduction Definition (Informal)

This process is known as reduction.

Since DAG-SPT can be used to DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

Algorithms by Dasgupta, Papadimitriou, and Vazirani defines a reduction informally as follows:

“If any subroutine for task Q can be used to solve P, we say P reduces to Q.”

Can also define the idea formally, but way beyond the scope of our class.

If you’re curious, you can read more about Karp and Cook reductions.

Reduction is more than sign flipping. In the bonus slides, we give an example of a richer reduction (3SAT to Independent Set)

61

62 of 72

Reductions

Earlier I claimed that the longest paths problem is potentially the most important unsolved question in mathematics.

This is true, but also a big misleading.
The reason: Vast numbers of important problems reduce to the longest paths problem!
But also: The longest path problem also reduces back to those!
In other words: Solving any of these problems solves them all.

We might revisit this idea (NP-Completeness) in the last week of class.

62

63 of 72

Reductions and Decomposition

Reductions are just a more formal version of what we’ve been doing throughout the course.

Percolation can be solved with Disjoint Sets.
Finding the hyponyms of a word can be solved with DFS (or BFS).

At its heart, computer science is about taking a complex task and breaking it into smaller parts.

Using appropriate abstractions makes problem solving vastly easier.

63

64 of 72

Generational Changes in the Human Mind

Interesting question: Are we regressing? Are LLMs partially to blame?

64

65 of 72

Reminder

Project 4C due Tuesday after Spring Break!.

65

66 of 72

Reduction to 3SAT (Optional CS170 Preview)

Lecture 25, CS61B, Spring 2026

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

Definition
Reduction to 3SAT (Optional CS170 Preview)

66

67 of 72

The Independent Set Problem

An independent set is a set of vertices in which no two vertices are adjacent.

The Independent-set Problem:

Does there exist an independent set of size k?
i.e. color k vertices red, such that none touch.

Example for the graph on the right and k = 9

For this particular graph, N=24.

67

68 of 72

The 3SAT Problem

3SAT: Given a boolean formula, does there exist a truth value for boolean variables that obeys a set of 3-variable disjunctive constraints?

68

Example: (x1 || x2 || !x3) && (x1 || !x1 || x1) && (x2 || x3 || x4)

Solution: x1 = true, x2 = true, x3 = true, x4 = false

3 variable disjunctive constraint�

69 of 72

3SAT Reduces to Independent Set

Proposition: 3SAT reduces to Independent-set.

Proof. Given an instance ϕ of 3-SAT, create an instance G of Independent-set:

For each clause in ϕ, create 3 vertices in a triangle.
Add an edge between each literal and its negation (can’t both be true in 3SAT means can’t be in same set in Independent-set)

69

Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)

x2

x1

x3

! x2

x4

! x1

! x4

x3

! x1

x3

x1

x4

k = number of variables = 4

70 of 72

3SAT Reduces to Independent Set

Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.

Reminder: An independent set of size 4 is a set of 4 (red) vertices that do not touch.

70

Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)

x2

x1

x3

! x2

x4

! x1

! x4

x3

! x1

x3

x1

x4

k = number of variables = 4

71 of 72

3SAT Reduces to Independent Set

Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.

Reminder: An independent set of size 4 is a set of 4 (red) vertices that do not touch.

71

Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)

x2

x1

x3

! x2

x4

! x1

! x4

x3

! x1

x3

x1

x4

k = number of variables = 4

72 of 72

Reduction

Since IND-SET can be used to solve 3SAT, we say that “3SAT reduces to IND-SET”.

Note: 3SAT is not a graph problem!
Note: Reductions don’t always involve creating graphs.

72

3SAT

Preprocess

IND-SET

G

IND-SET for G

Postprocess

Assignment so

that Φ gives true.

Φ

x1: true

x2: false

x3: false

x4: true