Give an example of an application of a graph in which determ

Give an example of an application of a graph, in which determining all pairs shortest paths would be of importance. Describe what the vertices, edges and edge weights of the graph represent. Explain the significance of the shortest path for such a graph and why it would be important.

Solution

Give an example of an application of a graph, in which determining all pairs shortest paths
would be of importance. Describe what the vertices, edges and edge weights of the graph
represent. Explain the significance of the shortest path for such a graph and why
it would be important.

Consider a network of computers through which you want to transfer data between nodes(systems).
This is a perfect example for a graph. Here it is required to determine the all pair shortest
path. The reason is, when some block of data need to be transferred between a pair of computers,
if known the shortest path between them(assume the minimum number of nodes as the shortest path),
the data can be transmitted at the earliest possible, and at the possible least cost.
Here the vertices are the computers, and the edges are the cables connecting the computers.
And the edge weights is the cost/time involved in transferring the data between a pair of
nodes if connected. If the shortest path between the pairs of computers is not known in this
case, we can\'t predict on the time/cost required to transfer the data between some pair of nodes.

Another general example(non-computer related) of a network is a transportation network would
it be a rail/road/air transport. The vertices represent the halts/stations/airports, the edges
represent the routes connected, and the edge weights represent the distance/time/ticket fare
involved to transit between a given pair or locations. And if the shortest path between
all-pairs is known, a person can transit between the required locations with the minimum
cost/time.