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: http://www.cs.gsu.edu/~cscazz/CS4520/index.htm. 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;
}