I'm working on a project implementing Dijkstra's Algorithm. The project involves reading from an input file and the format of the file is as follows:
- The first line of the file tells the number of total vertices and the number of edges (n, m) respectively.
- The rest of the file is as follows:
- A number all by itself on a line indicates a vertex
- A line with two numbers indicates the neighbor of that vertex and the length to that vertex from that neighbor
- An empty line indicates the end of the neighbors list for that vertex
The goal of the project is the find the shortest path from a single source (vertex 0) to all other vertices.
We have to test 2 different input files, one with 1,000 vertices and the other with 25,000 vertices. To check our answers, the professor said that the total sum of shortest path distances should be 625,349 for the file with 1,000 vertices and 10,721,073 for the file with 25,000 vertices. When I ran my code, I got 565,490 for the file with 1,000 vertices and around 13,000,000 for the file with 25,000 vertices (took 10 minutes to run this one). The input files can be found here:. Scroll a little bit down and you'll see under #11 he has the input files. I've been working on finding the problem for days, and can't find the problem .Please try to help me. Thanks! Here is my code:
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <fstream> #include <climits> #include <vector> #include <string> #include <sstream> #include <ctime> using namespace std; class dijkstra { private: //initializing variables and vectors int n; int m; int vertex[25000]; int dist[25000]; int mark[25000]; int prev[25000]; vector<int> vertex2; vector<int> neighbor; vector<int> length; //displays time double elapsed_time; time_t stop_time, start_time; public: //member functions that aid the main algorithm void read(); void initialize(); int extract_min(); void algorithm(); void print_dijkstra(); }; void dijkstra::read() { //There are two files you can test...uncomment and comment out as necessary ifstream myfile("1000.txt"); //ifstream myfile("25000.txt"); string line, str1, str2; int val1, val2, vert; //checking to see whether the file can be opened if(myfile.is_open()){ //starting reading from the file, line by line while(getline(myfile,line)) { //stringstream used to manipulate string inputs stringstream ss(line); //This extracts the neighbors and lengths and puts it in respective vector if ((line.length() > 5) && (!isalpha(line[0]))){ ss >> val1 >> val2; vertex2.push_back(vert); neighbor.push_back(val1); length.push_back(val2); } //This extracts the vertices from the file and stores it in the array else if ((line.length() > 0) && (line.length() < 6)){ ss >> vert; vertex[vert] = vert; } //This detects a blank line in the file else if (line.length() == 0) ; //This extracts the total number of vertices and edges from the first line else { ss >> str1 >> str2; n = atoi((str1.substr(2,(str1.length()-2))).c_str()); m = atoi((str2.substr(2,(str2.length()-2))).c_str()); //Reserve the vector capacity as soon as the values are extracted vertex2.reserve(m); neighbor.reserve(m); length.reserve(m); for (int i = 0; i < n; i++) vertex[i] = INT_MAX; } } } } //end read //A member function that makes all the necessary initializations void dijkstra::initialize() { //Initialize the source's distance to be 0 int source = 0; dist[source] = 0; //Initialize the rest to have 0 and fill the predecessor array for(int i = 1; i < n; i++) { dist[i] = INT_MAX; prev[i] = 0; } //Initialize the mark array for (int i = 0; i < n; i++) mark[i] = 0; } //end initialize //This member functions executes Dijkstra's algorithm void dijkstra::algorithm() { //initialize all the variables int u; int alt; int temp; int count = 0; int globalindex; elapsed_time = 0.0; //Call initialize to begin the filling process initialize(); //Start the timer time(&start_time); //Makes the loop go up to n vertices while (count < n) { //return index of smallest distance left u = extract_min(); //cout << "count = " << count << " " << u << " at distance: " << dist[u] << endl; //finds aand returns the first index of the found vertex for(int i = 0; i < vertex2.size(); i++) { if(vertex2[i]== u){ globalindex = i; break; } } //Make sure the vertex wasn't already processed if (mark[u]!= 1) { //Running the parallel vectors and finding the shortest distances while(vertex2[globalindex] == vertex[u]) { //Add up the length with the current distance alt = dist[u] + length[globalindex]; temp = neighbor[globalindex]; //If that length is smaller than the current distance if (alt < dist[temp]) { //replace it dist[temp] = alt; prev[temp] = vertex[u]; } //Increment globalindex globalindex++; } //Mark the vertex as processed mark[u] = 1; } // end if //Increment count count++; } //Stop the timer time(&stop_time); } //end algorithm //This member function extracts the index of the smallest distance left int dijkstra::extract_min() { //Set the min to have the largest int value int min = INT_MAX; int index; for (int i = 0; i < n; i++) { if(mark[i] != 1 && dist[i] != INT_MAX) { //if the minimum is greater than the current distance if(min > dist[i]) { //replace min with the shorter distance min = dist[i]; index = i; } } } //return the index of the smallest remaining distance return index; } //This member function prints out the shortest path distances from source to every node void dijkstra::print_dijkstra() { int pathsum = 0; int sum = 0; //loop through and add all the distances for (int i = 1; i < n; i++) { if (dist[i] != INT_MAX) { pathsum = dist[i]; //display distance from 0 to each node cout << "Shortest path from source 0 to " << i << " is " << pathsum << endl; //keep adding to the total sum of lengths sum += pathsum; } //no path exists from 0 to vertex if the above statement fails else cout << "There is no path from source 0 to " << i << endl; } //print out the total length and time taken cout << "\nThe total path length is: " << sum << endl; elapsed_time = difftime(stop_time, start_time); cout << "\n\nTime taken: " << elapsed_time << " second(s)\n" <<endl; } void main() { int i; //used to keep executable window open dijkstra s; s.read(); s.algorithm(); s.print_dijkstra(); cin >> i; }