2nd Shortest Path Algorithm

This assignment involves extension to the single source - single destination shortest path problem.

The Program

Your program should:

1. Read the name of a text file from the console.

2. Read a graph from the file.

3. Find the shortest path between the start and goal vertices specified in the file.

4. Print out the vertices on the path, in order from start to goal.

5. Print out the length of this path.

6. Devise a strategy for determining the second shortest path between the vertices.

7. Find the second shortest path between the start and goal vertices specified in the file.

8. Print out the vertices on the path, in order from start to goal.

9. Print out the length of this path.

The data files are constructed as follows:

• Two integers: nVertices and nEdges, the number of vertices and edges in the graph.
• nVertices triples consisting of the label and the x- and y-coordinates of each vertex.
• nEdges triples consisting of the labels of the start and end vertices of each edge, along with its weight. Note: the weight associated with an edge will be greater than or equal to the Euclidean distance between its start and end vertices as determined by their coordinates.
• Two labels, the indicating the start and goal vertices for which the paths are required.

A proposed solution to the second shortest path problem is as follows:

For each edge ei on the shortest path:
Find the shortest path on (V, E – {ei}). // shortest path without edge ei
The shortest of these is the second shortest path.

Questions

Is this proposed solution correct?

1. If we require that the second shortest path be longer than the shortest path?

2. If the graph contains cycles?

3. If the graph is undirected?

In each case explain your answer and, if necessary explain how you might modify the proposed algorithm to address any issues you identify.

Note: you may implement either the proposed solution or any modification you develop. You are not required to implement a modified proposal if you do not wish to do so.