Shortest Path
This assignment involves extension to the single source – singledestination 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 betweenthe vertices.
7. Find the second shortest path between the start and goal vertices specifiedin 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 andedges in the graph.
• nVertices triples consisting of the label and the x- and ycoordinates of each vertex.
• nEdges triples consisting of the labels of the start and end vertices ofeach edge, along with its weight. Note: the weight associated with anedge 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 whichthe 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 – {e i}). // shortest path without edgeei.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 modifythe proposed algorithm to address any issues you identify.
Programs must compile and run under g++ (C++ programs)
Programs should be appropriately documented with comments.
Program should be implemented in single .cpp file.
Standard libraries of data structures andalgorithms such as STL may not be used, nor may code be sourced fromtextbooks, the internet, etc.
Standard libraries of data structure and algorithm such as STL may not be used.
Solution
The documentation for program
Description of the overall solution strategy for the shortest path problem.
Algorithm to find the shortest path between a and b. It picks the unvisited vertex
with the lowest distance, calculates the distance through it to each unvisited
neighbor, and updates the neighbor’s distance if smaller. Mark visited when done
with neighbors.
Description of the overall solution strategy for the second shortest path
problem.
The solution same as previously, but we find first shortest path, remove it from graph
matrix and repeat search algorithm with updated graph.
Used data structures:
Struct ‘Vertex’ is used for saving of vertex description. It allows convert matrix index into
label.
Struct Vertex
{
char label;
int x;
int y;
};
I used dynamic arrays for saving graph matrix and algorithm results such as
distances cost and path storage.
int* adjacency_matrix;
int* distances; // array of distances from i vertex to end vertex
int* prev; // array of previous vertex
A list of any algorithms used
Dijkstra’s algorithm is used to determinate array of distances from each vertex to goal
vertex. The Dijkstra’s algorithm is most popular and effective algorithm of graph search.
b) Questions
1. If we require that the second shortest path be longer than the shortest path?
We should remove founded path till new founded path is same as shortest path
2. If the graph contains cycles?
Dijkstra’s algorithm has no deal with cycles so we no need modify program.
3. If the graph is undirected?
We should modify adjacency matrix filling algoritm to have mirror values for eachvertices.
main.cpp
#include
#include
#include
#include
#include
struct Vertex
{
char label;
int x;
int y;
};
using namespace std;
#define UNDEFINED -1
#define INFINITE_DISTANCE 1000000
int label_to_adjacency_matrix_index(char label, Vertex* vertices, int size)
{
return label – ‘a’;
}
void Dijkstra(int* adjacency_matrix, int nVertices, int goalVertexIndex, int* distances, int* prev)
{
// array of visited vertices
bool* visitedVertices = new bool[nVertices];
int i = 0;
// Initialization
for (i = 0; i < nVertices; i++)
{
prev[i] = UNDEFINED; // Previous vertex in optimal path from ‘i’
visitedVertices[i] = false; // All vertices mark as unvisited
distances[i] = INFINITE_DISTANCE; // Unknown distance from ‘i’ to ‘end vertex’
}
// distance from ‘end vertex’ to ‘end vertex’ is zero
distances[goalVertexIndex] = 0;
int minindex, min;
int alt;
// algorithm step
do
{
minindex = UNDEFINED; //
min = INFINITE_DISTANCE; //
// find unvisited vertex with minimal path cost
for (i = 0; i < nVertices; i++)
{
if ((!visitedVertices[i]) &&
(distances[i] < min))
{
// Update minimal values
min = distances[i];
minindex = i;
}
}
// if we can found candiate vertex
if (minindex != UNDEFINED)
{
// check values
for (i = 0; i < nVertices; i++)
{
// check path from i vertex to minindex
if (adjacency_matrix[i * nVertices + minindex] > 0)
{
// calculate path cost
// adjacency_matrix[i * nVertices + minindex] – cost of path from i vertex to minindex
// min – cost of path from minindex to endVertex
alt = min + adjacency_matrix[i * nVertices + minindex];
// distances[i] – cost of path from i to endVertex
if (alt < distances[i])
{
distances[i] = alt;
prev[i] = minindex;
}
}
visitedVertices[minindex] = true;
}
}
} while (minindex > 0);
delete []visitedVertices;
}
void DisplayShortestPath(int* adjacency_matrix, int nVertices, Vertex* vertices,
int startVertexIndex, int endVertexIndex, int* distances, int* prev)
{
Dijkstra(adjacency_matrix, nVertices, endVertexIndex, distances, prev);
cout << “Cost: ” << distances[startVertexIndex] << endl;
int vertexIndex = startVertexIndex;
do
{
cout << vertices[vertexIndex].label << “(” << vertices[vertexIndex].x << “, ” << vertices[vertexIndex].y << “) -> “;
vertexIndex = prev[vertexIndex];
}
while (vertexIndex != endVertexIndex);
cout << vertices[vertexIndex].label << “(” << vertices[vertexIndex].x << “, ” << vertices[vertexIndex].y << “)” << endl;
}
int main()
{
string file_name;
cout << “Please enter file name:\n>”;
getline(cin, file_name);
ifstream in(file_name);
if (!in)
{
return -1;
}
int nVertices = 0, nEdges = 0;
// read edges and vertices count from file
in>>nVertices>>nEdges;
Vertex* vertices = new Vertex[nVertices];
int i = 0;
// read vertices from file
for ( i = 0; i < nVertices; i++)
{
in >> vertices[i].label >> vertices[i].x >> vertices[i].y;
}
// adjancency matrix for graph
int* adjacency_matrix = new int[nVertices * nVertices];
for (i = 0; i < nVertices * nVertices; i++)
{
adjacency_matrix[i] = 0; // initialize adjancency matrix
}
// read edges from file
for (i = 0; i < nEdges; i++)
{
char startVertex = 0;
char endVertex = 0;
int distance = 0;
in >> startVertex >> endVertex >> distance;
// convert human readable labels into matix index
int startVertexIndex = label_to_adjacency_matrix_index(startVertex, vertices, nVertices);
int endVertexIndex = label_to_adjacency_matrix_index(endVertex, vertices, nVertices);
adjacency_matrix[startVertexIndex * nVertices + endVertexIndex] = distance;
}
char startVertexLabel = 0;
char endVertexLabel = 0;
// read two labels, the indicating the start and goal vertices for which the paths are required.
in >> startVertexLabel >> endVertexLabel;
int startVertexIndex = label_to_adjacency_matrix_index(startVertexLabel, vertices, nVertices);
int endVertexIndex = label_to_adjacency_matrix_index(endVertexLabel, vertices, nVertices);
// array of distances from i vertex to end vertex
int* distances = new int[nVertices];
// array of previous vertex
int* prev = new int[nVertices];
// find and display shortest path
DisplayShortestPath(adjacency_matrix, nVertices, vertices, startVertexIndex, endVertexIndex, distances, prev);
// remove founded shortest path from adjacency matrix
int vertexIndex = startVertexIndex;
do
{
int startNode = vertexIndex;
vertexIndex = prev[vertexIndex];
int endNode = vertexIndex;
// remove edge from adjacency matrix
adjacency_matrix[startNode * nVertices + endNode] = 0;
}
while (vertexIndex != endVertexIndex);
// after removing we get matrix (V, E – {e i}).
// find and display the second shortest path
DisplayShortestPath(adjacency_matrix, nVertices, vertices, startVertexIndex, endVertexIndex, distances, prev);
// free allocated arrays
delete []distances;
delete []prev;
delete []adjacency_matrix;
delete []vertices;
return 0;
}