Section 7.3 Shortest Path and Minimal Spanning Tree
581
d. Using the result from part (c), prove that in graph H, degree( p) + degree(q) < n.
e. Prove that in graph G, degree( p) + degree(q) < n.
f. Conclude from part (e) that G has a Hamiltonian circuit.
38. Ore’s theorem (Exercise 37) gives a sufficient condition for a Hamiltonian circuit to exist, but it is not a
necessary condition. Find a simple graph G with n nodes, n ≥ 3, that has a Hamiltonian circuit but for
which condition (2) does not hold.
S e c t i o n 7 . 3 ShorteSt Path and MiniMal SPanning tree
Shortest-Path Problem
Assume that we have a simple, weighted, connected graph, where the weights are
positive. Then a path exists between any two nodes x and y. Indeed, there may be
many such paths. The question is, How do we find a path with minimum weight?
Because weight often represents distance, this problem has come to be known as
the “shortest-path” problem. It is an important problem to solve for a computer
or communications network, where information at one node must be routed to
another node in the most efficient way possible, or for a transportation network,
where products in one city must be shipped to another.
The traveling salesman problem is a minimum-weight path problem with such
severe restrictions on the nature of the path that such a path may not exist at all.
In the shortest-path problem, we put no restrictions (other than minimum weight)
on the nature of the path, and because the graph is connected, we know that such
a path exists. For this reason we may hope for an efficient algorithm to solve the
problem, even though no such algorithm is known for the traveling salesman problem. Indeed such an algorithm does exist; it was published in 1959 by Edsger W.
Dijkstra, a prominent computer scientist of the twentieth century.
The shortest-path algorithm known as Dijkstra’s algorithm works as follows.
We want to find the minimum-distance path from a given node x to a given node
y. We build a set (we’ll call it IN) that initially contains only x but grows as the
algorithm proceeds. At any given time IN contains every node whose shortest
path from x, using only nodes in IN, has so far been determined. For every node z
outside IN, we keep track of the shortest distance d 3z 4 from x to that node, using
a path whose only non-IN node is z. We also keep track of the node adjacent to z
on this path, s 3z 4.
How do we let IN grow; that is, which node should be moved into IN next?
We pick the non-IN node with the smallest distance d. Once we add that node,
call it p, to IN, then we have to recompute d for all the remaining non-IN nodes,
because there may be a shorter path from x going through p than there was before
p belonged to IN. So we compare the current distance of z from x, d 3z 4, with the
distance of p from x, d 3 p 4, plus the distance from p to z, A3 p, z 4 where A is the
adjacency matrix. If there is a shorter path, we must also update s 3z 4 so that p is
now shown to be the node adjacent to z on the current shortest path, that is, s 3z 4
is the node just before z on this path from x. As soon as y is moved into IN, IN
stops growing. The current value of d 3 y 4 is the distance for the shortest path, and
its nodes are found by looking at y, s 3 y 4, s 3s 3 y 4 4, and so forth, until we have traced
the path back to x.
A pseudocode form of the algorithm is given in the accompanying box. The
input is the adjacency matrix for a simple, connected graph G with positive weights
581
d. Using the result from part (c), prove that in graph H, degree( p) + degree(q) < n.
e. Prove that in graph G, degree( p) + degree(q) < n.
f. Conclude from part (e) that G has a Hamiltonian circuit.
38. Ore’s theorem (Exercise 37) gives a sufficient condition for a Hamiltonian circuit to exist, but it is not a
necessary condition. Find a simple graph G with n nodes, n ≥ 3, that has a Hamiltonian circuit but for
which condition (2) does not hold.
S e c t i o n 7 . 3 ShorteSt Path and MiniMal SPanning tree
Shortest-Path Problem
Assume that we have a simple, weighted, connected graph, where the weights are
positive. Then a path exists between any two nodes x and y. Indeed, there may be
many such paths. The question is, How do we find a path with minimum weight?
Because weight often represents distance, this problem has come to be known as
the “shortest-path” problem. It is an important problem to solve for a computer
or communications network, where information at one node must be routed to
another node in the most efficient way possible, or for a transportation network,
where products in one city must be shipped to another.
The traveling salesman problem is a minimum-weight path problem with such
severe restrictions on the nature of the path that such a path may not exist at all.
In the shortest-path problem, we put no restrictions (other than minimum weight)
on the nature of the path, and because the graph is connected, we know that such
a path exists. For this reason we may hope for an efficient algorithm to solve the
problem, even though no such algorithm is known for the traveling salesman problem. Indeed such an algorithm does exist; it was published in 1959 by Edsger W.
Dijkstra, a prominent computer scientist of the twentieth century.
The shortest-path algorithm known as Dijkstra’s algorithm works as follows.
We want to find the minimum-distance path from a given node x to a given node
y. We build a set (we’ll call it IN) that initially contains only x but grows as the
algorithm proceeds. At any given time IN contains every node whose shortest
path from x, using only nodes in IN, has so far been determined. For every node z
outside IN, we keep track of the shortest distance d 3z 4 from x to that node, using
a path whose only non-IN node is z. We also keep track of the node adjacent to z
on this path, s 3z 4.
How do we let IN grow; that is, which node should be moved into IN next?
We pick the non-IN node with the smallest distance d. Once we add that node,
call it p, to IN, then we have to recompute d for all the remaining non-IN nodes,
because there may be a shorter path from x going through p than there was before
p belonged to IN. So we compare the current distance of z from x, d 3z 4, with the
distance of p from x, d 3 p 4, plus the distance from p to z, A3 p, z 4 where A is the
adjacency matrix. If there is a shorter path, we must also update s 3z 4 so that p is
now shown to be the node adjacent to z on the current shortest path, that is, s 3z 4
is the node just before z on this path from x. As soon as y is moved into IN, IN
stops growing. The current value of d 3 y 4 is the distance for the shortest path, and
its nodes are found by looking at y, s 3 y 4, s 3s 3 y 4 4, and so forth, until we have traced
the path back to x.
A pseudocode form of the algorithm is given in the accompanying box. The
input is the adjacency matrix for a simple, connected graph G with positive weights