Consider a data communication network that must route data packets (email, MP3 files, or videofiles, for example). Such a network consists of routers connected by physical cables or links. Arouter can act as a source, a destination, or a forwarder of data packets. We can model a networkas a graph with each router corresponding to a vertex and the link or physical connection betweentwo routers corresponding to apair of directed edgesbetween the vertices.A network that follows the OSPF (Open Shortest Path First) protocol routes packets usingDijkstra’s shortest path algorithm. The criteria used to compute the weight corresponding to alink can include the time taken for data transmission, reliability of the link, transmission cost, andavailable bandwidth. Typically each router has a complete representation of the network graphand associated information available to it.For the purposes of this project, each link has associated with it the transmission time takenfor data to get from the vertex at one end to the vertex at the other end. You will compute thebest path using the criterion of minimizing the total time taken for data to reach the destination.The shortest time path minimizes the sum of the transmission times of the links along the path.The network topology can change dynamically based on the state of the links and the routers.For example, a link may go down when the corresponding cable is cut, and a vertex may go downwhen the corresponding router crashes. In addition to these transient changes, changes to a networkoccur when a link is added or removed.
There are five tasks in this project: building the initial graph, updating the graph to reflect changes,finding the shortest path between any two vertices in the graph based on its current state, printingthe graph, and finding reachable sets of vertices. These are described in turn.