Reference no: EM133300631

Using a variant of matrix multiplication to solve a the all-pair shortest paths problem provides a very rich tool to solve a lot of problems. Before converting the problem from graph form to matrix form, we replace G by an augmented version GA which has additional edges: an edge of weight zero from every vertex to itself, and edges of weight -inf between every two vertices in G that do not share an edge. Then the modified matrix multiplication algorithm (discussed in class) is used (*' means +, and +' means minimum).

A function call is made to AllPairsSP(G, E, W, 0, inf , +, min) in this instant. In general, the function call can be made to AllPairsSP(G, E, W, diagW, uncW, mult(), add() ). By changing the arguments to the call other problems can be solved.

1. Set the arguments of AllPairsSP so that the path with the minimum number of edges between every pair of vertices is produced.

2. We define the average path density -APD- as the sum of a path edges weights divided by the number of edges in the path. For example the path from A to B: A --> 10--> X--> 8--> Y--> 6 --> B has an APD of (10+8+6)/3 = 8. Modify AllPairsSP to calculate the minimum APD between every two nodes,