Given a directed graph , we would like to find all-pairs shortest path lengths which are the all shortest path lengths between every pair of vertices, where the size of the set . Let denote a directed edge from a vertex to a vertex , and denote the length of the edge . The graph may have a negative length edge but does not have any negative length cycle. The length of the edge from the vertex to the same vertex , and when there exists no edge from the vertex to the vertex , .
Algorithm 1 on the next page outputs the single-source shortest path lengths. Let be a single source vertex, the shortest path length from the vertex to a vertex is stored in . Algorithm 2 outputs the all-pairs shortest path lengths table , where the length of the shortest path from a vertex to a vertex is stored in . Each algorithm uses and to store interim results, respectively. Answer the following questions.
(1) Apply Algorithm 1 to the graph in Figure 1 to obtain the shortest path length from a single-source vertex . Table 1 shows in Algorithm 1. Show the single-source path length , and from the single-source vertex .
(2) Apply Algorithm 2 to the graph in Figure 1 to obtain the all-pairs shortest path lengths. Table 2 shows in Algorithm 2. Show the selected vertex in the Main Loop and the corresponding table , and .
(3) To obtain all-pairs shortest path lengths, consider Algorithm 1-ALL which applies Algorithm 1 for all vertices in as a single-source vertex. Compare Algorithm 1-ALL and Algorithm 2.
