For this assignment, you will implement the shortest path algorithm demonstrated

Question

For this assignment, you will implement the shortest path algorithm demonstrated in class (Dijkstra's algorithm). You will take the Graph class I showed you and fill in the shortestPath method. The method should return a vector of node pointers, where each pointer is a stop in the path. For example, if you are finding a path from node A to node E, and the path goes through nodes B, C, and D, in that order, the return value should be a vector whose values are:

[A, B, C, D, E]

Things you should understand very well going into this assignment:

Dijkstra's algorithm for finding the shortest path.

Using ADTs - specifically deque, unordered_set, vector, and unordered_map.

Using iterators to go through an ADT one element at a time.

Throwing exceptions.

Templates.

Pointers.

NOTE: You'll have to use std:: in front of every ADT you use - std::vector, std::deque, etc.

If you are feeling fuzzy on any of the above, please come to office hours so the TAs or I can help you!

Starter files:

graph.h - The Graph class, with nothing in the shortestPath method. This is the part you fill in!

main.cpp - A simple file that makes use of the Graph class, including the shortestPath method. Make sure you test edge cases (e.g. when a node doesn't exist, when there is no path between the two nodes, etc.).

Explanation / Answer

Hi,

Below is the program:

Since you have not provided me your graph class,i have implemented it myself and giving you the entire program.

Program:

#include<iostream>
#define INFINITY 9999

using namespace std;

class Dijkstra{
private:
int adjcencyMatrix[25][25];
int predecessor[15],distance[15];
bool mark[15];
int source;
int numberOfVertices;
public:
  
void read();


void initialize();

  

int getClosestUnmarkedNode();
  

void calculateDistance();
  

void output();
void printPath(int);
};


void Dijkstra::read(){
cout<<"Enter the number of vertices of the graph,should be > 0 ";
cin>>numberOfVertices;
while(numberOfVertices <= 0) {
cout<<"Enter the number of vertices of the graph,should be > 0 ";
cin>>numberOfVertices;
}
cout<<"Enter the adjacency matrix for the graph ";
cout<<"To enter infinity enter value: "<<INFINITY<<endl;
for(int row=0;row<numberOfVertices;row++) {
cout<<"Enter Positive weights for the row "<<row<<endl;
for(int column=0;column<numberOfVertices;column++) {
cin>>adjcencyMatrix[row][column];
while(adjcencyMatrix[row][column]<0) {
cout<<"Weights should be positive ,Enter the weight again ";
cin>>adjcencyMatrix[row][column];
}
}
}
cout<<"Enter the source vertex ";
cin>>source;
while((source<0) && (source>numberOfVertices-1)) {
cout<<"Source vertex should be between 0 and"<<numberOfVertices-1<<endl;
cout<<"Enter the source vertex again ";
cin>>source;
}
}


void Dijkstra::initialize(){
for(int value=0;value<numberOfVertices;value++) {
mark[value] = false;
predecessor[value] = -1;
distance[value] = INFINITY;
}
distance[source]= 0;
}


int Dijkstra::getClosestUnmarkedNode(){
int minDistance = INFINITY;
int closestUnmarkedNode;
for(int value=0;value<numberOfVertices;value++) {
if((!mark[value]) && ( minDistance >= distance[value])) {
minDistance = distance[value];
closestUnmarkedNode = value;
}
}
return closestUnmarkedNode;
}


void Dijkstra::calculateDistance(){
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count < numberOfVertices) {
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = true;
for(int i=0;i<numberOfVertices;i++) {
if((!mark[i]) && (adjcencyMatrix[closestUnmarkedNode][i]>0) ) {
if(distance[i] > distance[closestUnmarkedNode]+adjcencyMatrix[closestUnmarkedNode][i]) {
distance[i] = distance[closestUnmarkedNode]+adjcencyMatrix[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}


void Dijkstra::printPath(int node){
if(node == source)
cout<<(char)(node + 97)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl;
else {
printPath(predecessor[node]);
cout<<(char) (node + 97)<<"..";
}

void Dijkstra::output(){
for(int i=0;i<numberOfVertices;i++) {
if(i == source)
cout<<(char)(source + 97)<<".."<<source;
else
printPath(i);
cout<<"->"<<distance[i]<<endl;
}
}


int main(){
Dijkstra G;
G.read();
G.calculateDistance();
G.output();
return 0;
}

output:

Enter the number of vertices of the graph,should be >0

6

Enter the adjacency matrix for the graph

To enter infinity enter 9999

Enter the positive weights for row 0

0 4 2 9999 9999 9999

Enter the positive weights for row 1

4 0 1 5 9999 9999

Enter the positive weights for row 2

2 1 0 8 10 9999

Enter the positive weights for row 3

9999 5 8 0 2 6

Enter the positive weights for row 4

9999 9999 10 2 0 3

Enter the positive weights for row 5

9999 9999 9999 6 3 0

Enter the source vertex

0

a..c..b..d..e..f..->13

Explaination:

1.Function read() reads No of vertices, Adjacency Matrix and source Matrix from the user. The number of vertices must be greather than zero, all members of Adjacency Matrix must be postive as distances are always positive. The source vertex must also be positive from to noOfVertices - 1

2.Function initialize() initializes all the data members at the begining of the execution. The distance between source to source is zero and all other distances between source and vertices are infinity. The mark is initialized to false and predecessor is initialized to -1

3.Function getClosestUnmarkedNode returns the node which is nearest from thePredecessor marked node. If the node is already marked as visited, then it search for another node.

4.Function calculateDistance calculates the minimum distances from the source node to Other node.

5.Function output prints the results

Hope that helps...HAPPY ANSWERING!!!!!!!

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.