Introduction to Algorithms, Third Edition

Unweighted shortest path:
3
Find a path from
u
to
consisting of the fewest
edges. Such a path must be simple, since removing a cycle from a path pro-
duces a path with fewer edges.
3
We use the term “unweighted” to distinguish this problem from that of finding shortest paths with
weighted edges, which we shall see in Chapters 24 and 25. We can use the breadth-first search
technique of Chapter 22 to solve the unweighted problem.

---

382
Chapter 15
Dynamic Programming
q
r
s
t
Figure 15.6
A directed graph showing that the problem of finding a longest simple path in an
unweighted directed graph does not have optimal substructure. The path
q
!
r
!
t
is a longest
simple path from
q
to
t
, but the subpath
q
!
r
is not a longest simple path from
q
to
r
, nor is the
subpath
r
!
t
a longest simple path from
r
to
t
.
Unweighted longest simple path:
Find a simple path from
u
to
consisting of
the most edges. We need to include the requirement of simplicity because other-
wise we can traverse a cycle as many times as we like to create paths with an
arbitrarily large number of edges.
The unweighted shortest-path problem exhibits optimal substructure, as follows.
Suppose that
u
¤
, so that the problem is nontrivial. Then, any path
p
from
u
to
must contain an intermediate vertex, say
w
. (Note that
w
may be
u
or
.)
Thus, we can decompose the path
u
p
;
into subpaths
u
p
1
;
w
p
2
;
. Clearly, the
number of edges in
p
equals the number of edges in
p
1
plus the number of edges
in
p
2
. We claim that if
p
is an optimal (i.e., shortest) path from
u
to
, then
p
1
must be a shortest path from
u
to
w
. Why? We use a “cut-and-paste” argument:
if there were another path, say
p
0
1
, from
u
to
w
with fewer edges than
p
1
, then we
could cut out
p
1
and paste in
p
0
1
to produce a path
u
p
0
1
;
w
p
2
;
with fewer edges
than
p
, thus contradicting
p
’s optimality. Symmetrically,
p
2
must be a shortest
path from
w
to
. Thus, we can find a shortest path from
u
to
by considering
all intermediate vertices
w
, finding a shortest path from
u
to
w
and a shortest path
from
w
to
, and choosing an intermediate vertex
w
that yields the overall shortest
path. In Section 25.2, we use a variant of this observation of optimal substructure
to find a shortest path between every pair of vertices on a weighted, directed graph.
You might be tempted to assume that the problem of finding an unweighted
longest simple path exhibits optimal substructure as well. After all, if we decom-
pose a longest simple path
u
p
;
into subpaths
u
p
1
;
w
p
2
;
, then mustn’t
p
1
be a longest simple path from
u
to
w
, and mustn’t
p
2
be a longest simple path
from
w
to
? The answer is no! Figure 15.6 supplies an example. Consider the
path
q
!
r
!
t
, which is a longest simple path from
q
to
t
. Is
q
!
r
a longest
simple path from
q
to
r
? No, for the path
q
!
s
!
t
!
r
is a simple path
that is longer. Is
r
!
t
a longest simple path from
r
to
t
? No again, for the path
r
!
q
!
s
!
t
is a simple path that is longer.

---

15.3
Elements of dynamic programming
383
This example shows that for longest simple paths, not only does the problem
lack optimal substructure, but we cannot necessarily assemble a “legal” solution
to the problem from solutions to subproblems. If we combine the longest simple
paths
q
!
s
!
t
!
r
and
r
!
q
!
s
!
t
, we get the path
q
!
s
!
t
!
r
!
q
!
s
!
t
, which is not simple. Indeed, the problem of finding an unweighted
longest simple path does not appear to have any sort of optimal substructure. No
efficient dynamic-programming algorithm for this problem has ever been found. In
fact, this problem is NP-complete, which—as we shall see in Chapter 34—means
that we are unlikely to find a way to solve it in polynomial time.
Why is the substructure of a longest simple path so different from that of a short-
est path? Although a solution to a problem for both longest and shortest paths uses
two subproblems, the subproblems in finding the longest simple path are not