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;
}

hai!!!!!

am also trying to implement dijkstra algorithm.... still i dint get any solution.......
if u get any solution to this problem....... plz inform me.......................

there is an error showing up in this code can any1 help me plzzzzzz. its urgent .

//dj5.cpp:435: error: ‘::main’ must return ‘int’

#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;
}

Edited 3 Years Ago by mike_2000_17: Fixed formatting

This article has been dead for over six months. Start a new discussion instead.