Let us consider the Powerco example (Figure 2). Suppose that when power is sent from plant 1

Question:

Let us consider the Powerco example (Figure 2). Suppose that when power is sent from plant 1 (node 1) to city 1 (node 6), it must pass through relay substations (nodes 2–5).

For any pair of nodes between which power can be transported, Figure 2 gives the distance

(in miles) between the nodes. Thus, substations 2 and 4 are 3 miles apart, and power cannot be sent between substations 4 and 5. Powerco wants the power sent from plant 1 to city 1 to travel the minimum possible distance, so it must find the shortest path in Figure 2 that joins node 1 to node 6.

If the cost of shipping power were proportional to the distance the power travels, then knowing the shortest path between plant 1 and city 1 in Figure 2 (and the shortest path between plant i and city j in similar diagrams) would be necessary to determine the shipping costs for the transportation version of the Powerco problem discussed in Chapter 7.

image text in transcribed