Question: At the beginning of this chapter, you received the following assignment: You are the network administrator for a wide-area backbone network that serves your company's many offices across the country. Messages travel through the network by being routed from point to point until they reach their destination. Each node in the network therefore acts as a switching station to forward messages to other nodes according to a routing table maintained at each node. Some connections in the network carry heavy traffic, while others are less used. Traffic may vary with the time of day; in addition, new nodes occasionally come on line and existing nodes may go off line. Therefore you must periodically provide each node with updated information so that it can forward messages along the most efficient (that is, the least heavily traveled) route. How can you compute the routing table for each node?
You realize that you can represent the network as a weighted graph, where the arcs are the connections between nodes and the weights of the arcs represent traffic on the connections. The routing problem then becomes one of finding the shortest path in the graph from any node to any other node. Dijkstra's algorithm can be used to give the shortest path from any one node to all other nodes (see Exercise 9), so you could use the algorithm repeatedly with different start nodes. Or you could use Floyd's algorithm. Discuss the advantages and disadvantages of each approach, including an analysis of the order of magnitude of each approach.