Graphs and paths - Data Structures and Problem Solving Using Java - page 566

Explain how to modify Dijkstra's algorithm to produce a count of the
number of different minimum paths from v to w .

14.8

Explain how to modify Dijkstra's algorithm so that, if there is more than
one minimum path from v to w , a path with the fewest edges is chosen.

14.9

Give an example of when Dijkstra's algorithm gives the wrong
answer in the presence of a negative edge but no negative-cost cycle.

14.10

Consider the following algorithm to solve the negative-weighted,
shortest-path problem: Add a constant c to each edge cost, thus remov-
ing negative edges; calculate the shortest path on the new graph; and
then use that result on the original. What is wrong with this algorithm?

14.11

Suppose that in a directed graph, the cost of the path is the sum of the
edge costs on the path PLUS the number of edges on the path. Show
how to solve this version of the shortest path problem.

14.12

Prove the correctness of the negative-weighted, shortest-path algo-
rithm. To do so, show that when the eyeball visits vertex v for the i th
time, the value of D v is the length of the shortest weighted path con-
sisting of i or fewer edges.

14.13

Give a linear-time algorithm to find the longest weighted path in an
acyclic graph. Does your algorithm extend to graphs that have cycles?

14.14

Show that if edge weights are 0 or 1, exclusively, Dijkstra's algorithm
can be implemented in linear time by using a deque (Section 16.5).

14.15

Suppose all edge costs in a graph are either 1 or 2. Show that Dijkstra's
algorithm can then be implemented to run in linear time.

14.16

For any path in a graph, the bottleneck cost is given by the weight of the
shortest edge on the path. For example, in Figure 14.4, the bottleneck
cost of the path E , D , B is 23 and the bottleneck cost of the path E , D , C ,
A , B is 10. The maximum bottleneck problem is to find the path between
two specified vertices with the maximum bottleneck cost. Thus the max-
imum bottleneck path between E and B is the path E , D , B . Give an effi-
cient algorithm to solve the maximum bottleneck problem.

14.17

Let G be a (directed) graph and u and v be any two distinct vertices in
G . Prove or disprove each of the following.
a.

14.18

If G is acyclic, at least one of ( u , v ) or ( v , u ) can be added to the
graph without creating a cycle.

b. If adding one of either ( u , v ) or ( v , u ) to G without creating a cycle

is impossible, then G already has a cycle.