1 of 34

Lecture 16

Dynamic Programming IV

CSE 421 Autumn 2025

1

2 of 34

Previously…

2

3 of 34

Negative weights shortest path

Input: Directed graph and weights and a vertex

Output: For all vertices , the weight of the shortest path

3

For convenience, we’ll consider shortest paths to an endpoint, rather than from a source

(it’s the same thing up to inverting the direction of each edge)

Observation 1: If a path contains a negative weight cycle, then a shortest path doesn’t exist.

Observation 2: If has no negative cycles then there is a shortest path of length .

Proof: Any path of length has a cycle. That cycle has weight , so removing it only decreases the weight. Repeat until path is of length .

4 of 34

Bellman-Ford DP algorithm

What function should our DP algorithm make recursive calls to?

4

5 of 34

Bellman-Ford DP algorithm

The function: For , let be the length of the shortest path consisting of at most edges

5

Can we define the value at some points recursively based on the value at other points?

6 of 34

Bellman-Ford DP algorithm

The function: For , let be the length of the shortest path consisting of at most edges

6

Recursive structure/definition:

    • Case 1: The shortest path uses edges. Then��
    • Case 2: The shortest path uses exactly edges. Let be the first vertex on the path. Then��

7 of 34

Bellman-Ford DP algorithm

The function: For , let be the length of the shortest path consisting of at most edges

7

Recursive structure/definition:

The solution we are interested in is

8 of 34

Today

8

  • DP on graphs: shortest path on a graph with negative weights (Bellman-Ford continued)
  • Network flow

9 of 34

Bellman-Ford DP algorithm

(Assuming no negative cycles)

Filling the memo table:

    • Generate table of size and table of size
    • Set for and for all .
    • For to :
      • For :
        • Set .
        • For each edge :
          • If ,
            • Set and

Return output: The table contains the shortest path from each vertex to . For the actual path from to , follow from until it reaches .

9

Note: syntactically, this is ok because we first compute everything at the - layer, and then we consider the -th layer.

time and space?

10 of 34

Bellman-Ford DP algorithm

Filling the memo table:

    • Generate table of size and table of size
    • Set for and for all .
    • For to :
      • For :
        • Set .
        • For each edge :
          • If ,
            • Set and

Return output: The table contains the shortest path from each vertex to . For the actual path from to , follow from until it reaches .

(Assuming no negative cycles)

10

time and space?

time since, for each , we consider each edge once

space for the tables

11 of 34

Space saving

How might we save on space?

11

12 of 34

Space saving

Key observation: only depends on entries . Rows can be discarded!

12

So we can simply repeat the exact same algorithm as before, but discarding a row once we have used it. We will only ever keep two rows at once.

There’s an even more space efficient version where we keep a single row!

13 of 34

Bellman-Ford better DP implementation

(Assuming no negative cycles)

Filling the memo table:

    • Generate table of size and table of size
    • Set for and
    • For to :
      • For each edge :
        • If ,
          • Set and

Return output: The table contains the shortest path from each vertex to . For the actual path from to , follow from until it reaches .

13

Note: for each , we are repeating the same process.

14 of 34

Bellman-Ford better DP implementation

Filling the memo table:

    • Generate table of size and table of size
    • Set for and
    • For to :
      • For each edge :
        • If ,
          • Set and

Return output: The table contains the shortest path from each vertex to . For the actual path from to , follow from until it reaches .

(Assuming no negative cycles)

14

time still

space

15 of 34

Bellman-Ford better DP implementation

Filling the memo table:

    • Generate table of size and table of size
    • Set for and
    • For to :
      • For each edge :
        • If ,
          • Set and

Return output: The table contains the shortest path from each vertex to . For the actual path from to , follow from until it reaches .

(Assuming no negative cycles)

15

You may be worried by the fact that during round , we update values in as we go along. So, the later comparisons in that round, may involve already updated values, rather than the ones from round -1.

This is ok: in fact, it will make each converge faster to its true value.

16 of 34

Bellman-Ford correctness

16

Correctness of the first version with the larger table follows from our case analysis (+ induction). This shows that � = weight of shortest path with at most edges.

Correctness of the latest version follows from the fact that at the end of round we ensure (this can be shown similarly by induction):�1. weight of shortest path with at most edges.�2. is the weight of some valid path .

Putting 1 and 2 together with fact that there exists a shortest path of length -, means that, after round -, = weight of shortest path .

17 of 34

Even more savings

Observation: If doesn’t decrease in round , then we don’t need to consider any edges in round (as we’d be doing the same comparison as in the previous round). In other words, the paths through have already been considered.

  • Keep a queue of vertices updated in the previous round and only consider the edge if was in

17

Note what this means:

  • In round zero (base case), we set , and everything else stays as for .
  • In round 1, the only that can change are those that have a direct edge to .
  • In round 2, the only that can change are those that have a direct edge to something that changed in round 1.
  • And so on..

18 of 34

Even better DP implementation

(Assuming no negative cycles)

  • Compute the “reverse adjacency list”: For every , .
  • Generate tables , of size with , and
  • Initialize counter and generate a queue .
  • While :
    • Pop off the queue .
    • If , increment and push to .
    • Else, for each ,
      • If , set and
      • Push into queue (if not already there)

18

19 of 34

Bellman-Ford example

19

20 of 34

Bellman-Ford example

20

21 of 34

Bellman-Ford example

21

22 of 34

Bellman-Ford example

22

23 of 34

Bellman-Ford example

23

24 of 34

Bellman-Ford example

24

25 of 34

Bellman-Ford example

25

26 of 34

Bellman-Ford example

26

27 of 34

Bellman-Ford example

27

28 of 34

Bellman-Ford example

28

29 of 34

Bellman-Ford example

29

30 of 34

Bellman-Ford example

30

31 of 34

Bellman-Ford example

31

32 of 34

Bellman-Ford runtime

32

Note that the runtime is still in the worst case. Indeed, there are graphs where this is the runtime, e.g. complete graphs.

But, in practice the runtime can be much faster if you are dealing with graphs that have fewer than edges.

33 of 34

Bellman-Ford correctness

33

Correcteness of the original version with the larger table follows from our case analysis (+ induction). This shows that will contain the shortest path of with at most edges.

Correcteness of the latest version follows from the fact that at each round we are doing the same comparisons, except being clever about skipping comparisons that will for sure not result in an update.

34 of 34

Detecting negative cycles

34

Correctness tells us that after - iterations the value is the weight of the shortest path that uses - edges.

This is indeed the shortest path if there are no negative cycles (since we have argued earlier that, if there are no negative cycles, there is always a shortest path using - edges).

How can we slightly modify the algorithm to additionally detect if a negative cycle exists?

Do one additional round and check if any value gets updated! If so, then there must be a negative cycle. If not, no value will ever get updated again (since the next time we are doing the same comparisons again)