Shortest Path

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


  1. 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.

  1. 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.
  2. 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
  3. 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 <stdio.h>

#include <cstdlib>

#include <iostream>

#include <fstream>

#include <string>

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;

}