The figure that follows shows a partially complete layout for a circuit board of a large computer peripheral. Lines show channels along which circuits can be placed, together with the lengths of the channels in centimeters. Several circuits can be placed in a single channel (on different layers).

The last step in the design is to choose the routing from a component to be installed at point 1 to connections at points 8, 10, 11, and 12.

(a) Explain why this problem can be modeled as a shortest path problem.

(b) Explain why the most efficient procedure available from this chapter for computing optimal circuit routes is Dijkstra Algorithm 9C.

(c) Apply Algorithm 9C to compute optimal circuit routes to the 4 specified points.

Transcribed Image Text:

2 4 5 1 2 13 10 27 3 00 4 3 11 7 5 15 9 8 6 12 15 10 12