21.1 Label the following points in the plane 0 through 5, respectively: 
Taking edge lengths to be weights, consider the network defined by the edges 
Draw the network and give the adjacency-lists structure that is built by Program 20.5.
Show, in the style of Screenshot, all shortest paths in the network defined in Exercise 21.1.
21.3 Develop a network class implementation that represents the reverse of the weighted digraph defined by the edges inserted. Include a "reverse copy" constructor that takes a graph as parameter and inserts all that graph's edges to build its reverse.
21.4 Show that shortest-paths computations in networks with nonnegative weights on both vertices and edges (where the weight of a path is defined to be the sum of the weights of the vertices and the edges on the path) can be handled by building a network ADT that has weights on only the edges.
Find a large network online-perhaps a geographic database with entries for roads that connect cities or an airline or railroad schedule that contains distances or costs.
Write a random-network generator for sparse networks based on Program 17.12. To assign edge weights, define a random-edge-weight ADT and write two implementations: one that generates uniformly distributed weights, another that generates weights according to a Gaussian distribution. Write client programs to generate sparse random networks for both weight distributions with a well-chosen set of values of V and E so that you can use them to run empirical tests on graphs drawn from various distributions of edge weights.
21.7 Write a random-network generator for dense networks based on Program 17.13 and edge-weight generators as described in Exercise 21.6. Write client programs to generate random networks for both weight distributions with a well-chosen set of values of V and E so that you can use them to run empirical tests on graphs drawn from these models.
Implement a representation-independent network client that builds a network by taking edges with weights (pairs of integers between 0 and V - 1 with weights between 0 and 1) from standard input.
• 21.9 Write a program that generates V random points in the plane, then builds a network with edges (in both directions) connecting all pairs of points within a given distance d of one another (see Exercise 17.74), setting each edge's weight to the distance between the two points that that edge connects. Determine how to set d so that the expected number of edges is E.
21.10 Write a base class and derived classes that implement ADTs for graphs that may be undirected or directed graphs, weighted or unweighted, and dense or sparse.
21.11 The following table from a published road map purports to give the length of the shortest routes connecting the cities. It contains an error. Correct the table. Also, add a table that shows how to execute the shortest routes, in the style of Screenshot.
|
|
Providence
|
Westerly
|
New London
|
Norwich
|
|
Providence
|
-
|
53
|
54
|
48
|
|
Westerly
|
53
|
-
|
18
|
101
|
|
New London
|
54
|
18
|
-
|
12
|
|
Norwich
|
48
|
101
|
12
|
- |