Question

"Dijkstra's single-source shortest path algorithm returns a results grid that contains the lengths of the shortest paths from a given vertex [the source vertex] to the other vertices reachable from it. Develop a pseudocode algorithm that uses the results grid to build and return the actual [shortest] path, as a list of vertices, from the source vertex to a given [target] vertex. (Hint: This algorithm starts with a given vertex [the target vertex] in the grid's first column and gathers ancestor [parent] vertices, until the source vertex is reached.)"

*For your algorithm, assume that grid is the name of the results grid produced by Dijkstra's single-source shortest path algorithm.
*Each vertex is identified by its label/name, which is in column 1 of grid.
*As the first step of your algorithm, find the name of the source vertex.
*Next, get the name of the target vertex from the user.
Pseudocode should avoid details through broad-stroke statements. However, it must give enough information to outline the overall strategy.
In addition to showing your algorithm, answer the following questions: - In pseudocode, to find the source vertex, you can simply write: find source vertex Without providing code, explain how this would be accomplished in real code. - Did you run into any challenges? If so, what were they and how did you solve them? - Besides the given grid, did you have to use any other collection? If so, which one and why? If not, why not?

Answer 1

Algorithm:

Find the name of the source vertex from column 1 of grid.

Get the name of the target vertex from user input.

Initialize an empty list to store the path from source to target.

Add the target vertex to the end of the path list.

While the target vertex is not the source vertex: a. Find the row in grid that corresponds to the target vertex. b. For each ancestor vertex (parent) in the row: i. Check if the distance from the source vertex to the ancestor vertex plus the distance from the ancestor vertex to the target vertex equals the distance from the source vertex to the target vertex. ii. If it does, add the ancestor vertex to the beginning of the path list and set the target vertex to the ancestor vertex.

Return the path list.

To find the source vertex in real code, we can search for the vertex with the shortest distance from the source vertex in the results grid. This vertex will be the source vertex.

I did not run into any challenges in developing this algorithm.

No, I did not have to use any other collection for this algorithm since the path is stored in a list.

Step-by-step explanation: