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.
21.2 Show, in the style of Figure 21.3, 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.
21.5 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.
21.6 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.
21.8 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 Figure 21.4.
| | Providence | Westerly | New London | Norwich |
| Providence | “ | 53 | 54 | 48 |
| Westerly | 53 | “ | 18 | 101 |
| New London | 54 | 18 | “ | 12 |
| Norwich | 48 | 101 | 12 | “ |
