CS 624
Lecture 8: Dynamic Programming
We’re now going to investigate a general method of attacking a certain class of problems. The
method is called dynamic programming. It doesn’t work on every problem, and it’s not needed on
many problems. (For instance, we have very good methods of sorting, and we don’t need to use the
technique of dynamic programming to deal with this problem.) But where dynamic programming
is appropriate, it can often give extremely good results.
We’ll start out by talking about a particular problem. We’ll show how it can be solved using dynamic
programming. Then we’ll summarize the technique, and see how it can be applied to a couple of
other problems.
1 Shortest paths in weighted DAGs
I have to start out with a word of caution. There are many variations of this problem, and there
are many different algorithms that have been designed for these variations. So we need to be very
particular about exactly what the problem is, and exactly how we are going to approach it.
And I should say from the beginning that even though you may find another algorithm for this
particular problem, the one I am going to present here is essential for you to understand; and this
is for two reasons:
1. It is as efficient as any other algorithm you will find.
2. It is key to understanding dynamic programming in general, and in particular the other two
problems we will consider afterwards.
So here is the problem:
1. We have a DAG G.
2. Each edge e of G has associated with it a weight w(e). In our problem, it will always be true
that for each edge e, w(e) > 0. (There are other variations of the problem where this is not
true. We are not concerned with those cases.)
3. If n1 → n2 → · · · → np is a path in G (where of course each edge ni → nj is a directed edge
from ni to nj ), we define the cost of that path to be the sum of the weights of the edges on
that path.
1
, 2 1 SHORTEST PATHS IN WEIGHTED DAGS
4. Each node of G has a name. One of the nodes of GR is named start and another node is
named end.
5. There is at least one path from start to end.
6. The problem is to find the path of least cost from start to end.
Figure 1 shows a very simple example of a DAG like this.
n13 n5
15 12
16
start n10
20 14 16 22 35
21
n12 n11 n8 10 n2
3 5 11
17
8 12
n1 n6 28 n4
15 20 14
7 n9
6 18
11 20
n3 end
19
21
n7
Figure 1: A simple weighted DAG with distinguished start and end nodes
You can think of this kind of problem as a simplified version of what Google maps or the GPS
in a car does when you want to find the shortest path from where you are to some destination.
Lecture 8: Dynamic Programming
We’re now going to investigate a general method of attacking a certain class of problems. The
method is called dynamic programming. It doesn’t work on every problem, and it’s not needed on
many problems. (For instance, we have very good methods of sorting, and we don’t need to use the
technique of dynamic programming to deal with this problem.) But where dynamic programming
is appropriate, it can often give extremely good results.
We’ll start out by talking about a particular problem. We’ll show how it can be solved using dynamic
programming. Then we’ll summarize the technique, and see how it can be applied to a couple of
other problems.
1 Shortest paths in weighted DAGs
I have to start out with a word of caution. There are many variations of this problem, and there
are many different algorithms that have been designed for these variations. So we need to be very
particular about exactly what the problem is, and exactly how we are going to approach it.
And I should say from the beginning that even though you may find another algorithm for this
particular problem, the one I am going to present here is essential for you to understand; and this
is for two reasons:
1. It is as efficient as any other algorithm you will find.
2. It is key to understanding dynamic programming in general, and in particular the other two
problems we will consider afterwards.
So here is the problem:
1. We have a DAG G.
2. Each edge e of G has associated with it a weight w(e). In our problem, it will always be true
that for each edge e, w(e) > 0. (There are other variations of the problem where this is not
true. We are not concerned with those cases.)
3. If n1 → n2 → · · · → np is a path in G (where of course each edge ni → nj is a directed edge
from ni to nj ), we define the cost of that path to be the sum of the weights of the edges on
that path.
1
, 2 1 SHORTEST PATHS IN WEIGHTED DAGS
4. Each node of G has a name. One of the nodes of GR is named start and another node is
named end.
5. There is at least one path from start to end.
6. The problem is to find the path of least cost from start to end.
Figure 1 shows a very simple example of a DAG like this.
n13 n5
15 12
16
start n10
20 14 16 22 35
21
n12 n11 n8 10 n2
3 5 11
17
8 12
n1 n6 28 n4
15 20 14
7 n9
6 18
11 20
n3 end
19
21
n7
Figure 1: A simple weighted DAG with distinguished start and end nodes
You can think of this kind of problem as a simplified version of what Google maps or the GPS
in a car does when you want to find the shortest path from where you are to some destination.
