Project Title: Shortest Distance between cities of Pakistan

Write Abstract, Objective, Review, ALGORITHM and CONCLUSION of given below project code.

Project Title: Shortest Distance between cities of Pakistan

#include #include #include #include #include using namespace std; // STRUCT TO STORE CITY INDEX struct node { int value; // INDEX string name; // CITY NAME }; class Graph { private: list l1; // TO STORE CITY INDEXES int** array; // TO STORE SHORTEST PATH int** weight; // TO STORE GRAPH int** shortpath; // TO STORE PARENT PATH FOR SHOREST ROUTE int gsize; public: void create_graph() { ifstream file; file.open("B-20i1029-A5-GRAPH.txt"); file >> gsize; array = new int *[gsize]; // DYNAMIC POINTERS ARRAY weight = new int* [gsize]; shortpath = new int* [gsize]; for(int i=0;i> index ; file >> vertex; while(vertex!=-999) { file >> weights; weight[index][vertex] = weights; weight[vertex][index] = weights; array[index][vertex] = weights; array[vertex][index] = weights; shortpath[index][vertex] = index; shortpath[vertex][index] = vertex; file >> vertex; } } file.close(); // READING SECOND FILE TO STORE DATA IN LINKLIST file.open("B-20i1029-A5-CITY KEY.txt"); for(int i=0;i> n.value; getline(file,n.name,' '); l1.push_back(n); } } // USING FLOYD WARSHAL ALGORITHM TO FIND OUT SHORTEST PATHS void Floyd_Worshall_Alogrithm() { for(int k=0;karray[i][k]+array[k][j]) // IF SMALLER WAY FOUND { array[i][j]=array[i][k]+array[k][j]; // UPDATE WITH SHORTER VALUE shortpath[i][j] = shortpath[k][j]; // STORE THE PATH FROM WHERE IT WAS UPDATED } } } } } // PRINTING SHORTEST PATH BETWEEN TWO CITIES void print_Path(int x,int y) { cout <<"\t*************************************************************************************** "; cout <<"\t\tThe shortest path between these cities in kilometers is : "< s; while(y!=shortpath[x][y]&&y!=-1) { s.push(y); y = shortpath[x][y]; } int j=0; while(!s.empty()) { int z = s.top(); list::iterator i; for(i=l1.begin();i!=l1.end();i++) // TRAVERSING LIST FOR CITY NAME { node w = *i; if(w.value==z) { cout <<"\t\t\t"<<++j<<". "; w.name[1] = w.name[1]-32; // MAKING FIRST LETTER CAPITAL cout<< w.name<<" "; } } s.pop(); } cout <<"\t\t********************************************************************** "; } // FUNCTION TO GET INDEX OF THE ENTERED CITIES void city(string s1,string s2) { int a =-1,b =-1; list::iterator i; for(i=l1.begin();i!=l1.end();i++) // TRAVERSING LIST FOR INDEXES { node w = *i; if(w.name==s1) a = w.value; if(w.name==s2) b = w.value; } if(a==-1||b==-1) { cout <<"One of these cities not found on our map "; return; } else { print_Path(a,b); // CALLING FINCTION TO PRINT PATH BETWEEN THESE INDEXES } } }; // FUNCION TO PRINT MENU int menu() { cout <<"\t\t********************************************************************** "; cout <<"\t\t** ** "; cout <<"\t\t**\t1. PRESS 1 TO FIND THE SHORTEST ROUTE BETWEEN TWO CITIES ** "; cout <<"\t\t**\t2. PRESS ANY OTHER DIGIT TO EXIT ** "; cout <<"\t\t** ** "; cout <<"\t\t********************************************************************** "; int x; cout <<"\t\t\t"; cin >> x; return x; }