CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Help please with getting my dijkstra's algorithm sorted

  1. #1
    Join Date
    Mar 2011
    Posts
    7

    Help please with getting my dijkstra's algorithm sorted

    Code:
     #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <sstream>
    #include <list>
    #include <limits.h>
    
    
    using namespace std;
    
    
    
    class Node
    {
    public:
    	string name;
    	vector<string> edges;
    	vector<int> dist;
    };
    
    class Path
    {
    public:
    	vector <int> distance;
    	vector <string> fromwhere;
    	vector <int> complete;
    	vector <string> cities;
    	vector <int> currentdistance;
    	vector <string> path;
    };
    
    int main ()
    {
    	int c, i, j, k, num_of_cities, rows, totaldistance;
    	num_of_cities = 0;
    	totaldistance = 0;
    	string line, temp_name, temp_edge, temp_dist, temp_to, temp_from;
    	stringstream iss, source_to_dest;
    	vector<Node> nodes;
    	vector<string> lines, paths;
    	ifstream inFile("ukcities.txt");
    	Node temp_add;
    	i = 0;
    	j = 0;
    	rows = 0;
    	if (inFile)
    	{
    	while (getline(inFile, line, '\n'))
    	{
    		lines.push_back(line);
    		iss.clear();
    		iss << line;		
    		getline(iss, temp_name, '\t');
    		getline(iss, temp_edge, '\t');
    		getline(iss, temp_dist, '\t');
    		num_of_cities = nodes.size();
    			if (num_of_cities == 0)
    			{
    				temp_add.name = temp_name;
    				temp_add.edges.push_back(temp_edge);
    				const char *c_ptr=temp_dist.c_str();
    				temp_add.dist.push_back(atoi(c_ptr));
    				nodes.push_back(temp_add);
    				temp_add.name = temp_edge;
    				temp_add.edges.clear();
    				temp_add.dist.clear();
    				temp_add.edges.push_back(temp_name);
    				temp_add.dist.push_back(atoi(c_ptr));
    				nodes.push_back(temp_add);
    			}
    			else 
    			{
    				i = 0;
    				j = 0;
    				num_of_cities = nodes.size();
    				while (!(i >= num_of_cities) && (j==0))
    				{
    					if (nodes[i].name == temp_name)
    					{
    						j = 1;
    						const char *c_ptr=temp_dist.c_str();
    						nodes[i].dist.push_back(atoi(c_ptr));
    						nodes[i].edges.push_back(temp_edge);
    						i=0;
    
    						
    					}
    					else
    						i++;
    				}
    					if (j==0)
    					{
    						j = 1;
    						temp_add.edges.clear();
    						temp_add.dist.clear();
    						temp_add.name = temp_name;
    						temp_add.edges.push_back(temp_edge);
    						const char *c_ptr=temp_dist.c_str();
    						temp_add.dist.push_back(atoi(c_ptr));
    						nodes.push_back(temp_add);
    						
    						i = 0;
    					}
    						i = 0;
    						j = 0;
    						num_of_cities = nodes.size();
    						while (!(i >= num_of_cities) && (j==0))
    						{
    							if (nodes[i].name == temp_edge)
    							{
    								j = 1;
    								temp_add.edges.clear();
    								temp_add.dist.clear();
    								const char *c_ptr=temp_dist.c_str();
    								nodes[i].dist.push_back(atoi(c_ptr));
    								nodes[i].edges.push_back(temp_name);
    								i=0;
    								
    							}
    							else
    								i++;
    						}
    						if (j==0)
    						{
    							temp_add.edges.clear();
    							temp_add.dist.clear();
    							temp_add.name = temp_edge;
    							temp_add.edges.push_back(temp_name);
    							const char *c_ptr=temp_dist.c_str();
    							temp_add.dist.push_back(atoi(c_ptr));
    							nodes.push_back(temp_add);
    							i=0;
    						}
    					
    				}
    			}
    		iss.clear();
    		
    	}
    	for (k = 0; k != num_of_cities; k++)
    	{
    
    		cout << nodes[k].name << '\n';
    	}
    
    	ifstream inPathFile("findpath.txt");
    	
    	while (getline(inPathFile, line, '\n'))
    	{
    		int number_of_edges, min, wheremin, count, l, m;
    		string prev_citie;
    		Path distances;
    		Path add_distances;
    		vector <string> pathtaken;
    		vector <int> pathdistance;
    		vector<string>::iterator it;
    		number_of_edges = 0;
    		wheremin = 0;
    		m= 0;
    		num_of_cities = nodes.size();
    		paths.push_back(line);
    		iss.clear();
    		iss << line;		
    		getline(iss, temp_from, '\t');
    		getline(iss, temp_to, '\t');
    		cout << "meow" << '\n';
    		i = 0;
    		j = 0;
    		for (j=0; j< num_of_cities; j++)
    		{
    		add_distances.distance.push_back(INT_MAX);
    		add_distances.complete.push_back(0);
    		add_distances.cities.push_back(nodes[j].name);
    		}
    		distances = add_distances;
    		distances.path.push_back(temp_from);
    		distances.currentdistance.push_back(0);
    		distances.fromwhere.push_back(temp_from);
    		i=0;
    		j=0;
    		k=0;
    		m=0;
    		l=0;
    		min = INT_MAX;
    		while ( (i < num_of_cities) && (temp_from != temp_to))
    		{
    			cout << temp_from;
    			if (temp_from == nodes[i].name)
    			{
    				distances.complete[i] = 1;
    				for (j=0; j < nodes[i].edges.size(); j++)
    				{
    					for(k=0; k < num_of_cities; k++)
    					{
    						if (nodes[i].edges[j] == distances.cities[k])
    						{
    						if (distances.distance[k] > nodes[i].dist[j]+distances.currentdistance[distances.currentdistance.size()-1])
    							distances.distance[k] = nodes[i].dist[j]+distances.currentdistance[distances.currentdistance.size()-1];
    							
    						}
    					}
    				}
    				for (l = 0; l < (distances.distance.size()); l++)
    				{
    					if ((distances.distance[l] + distances.currentdistance[distances.currentdistance.size()-1] < min) && (distances.distance[l]  != 0))
    					{
    						if (distances.distance[l] != INT_MAX)
    						{
    							if (distances.complete[l]  == 0)
    							{
    							min = distances.distance[l];
    							wheremin = l;
    							}
    						}
    					}
    				}
    				distances.complete[wheremin] = 1;
    				distances.currentdistance.push_back(min);
    				distances.path.push_back(nodes[wheremin].name);
    	
    				temp_from = nodes[wheremin].name;
    				i= 0;
    				j=0;
    				k=0;
    				min = INT_MAX;
    			}
    			else
    				i++;
    		}
    		cout << "done";
    		
    	}
    	cin >> c;
    	return 0;
    
    }



    This is what i have so far, i'm finding it hard to print out the path it takes and the total distance. Please give me help!
    Attached Files Attached Files

  2. #2
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Help please with getting my dijkstra's algorithm sorted

    Well, I give you good marks for using standard library containers instead of coding your own.

    However, your program is not modular -- it is just one giant main() function, and very few, if anyone is going to wade through all of that code and determine what you are doing. You should have broken your program up into functions, so that each piece can be worked on and fixed, independent of the other pieces of the program.

    So the first thing I suggest you do is write a function that does what you say you can't do. At the very least, we have something to work with that is confined enough to a single enitity.
    Code:
    void PrintPath(const Path& myPath, const Node& fromNode, const Node& toNode)
    {
        // code to print the path from one node to another
    }
    Now you pass the pass and the from/to nodes. Then all this function does is print the path, and we don't have to see all of that other stuff you're doing.

    Regards,

    Paul McKenzie

  3. #3
    Join Date
    Mar 2011
    Posts
    7

    Re: Help please with getting my dijkstra's algorithm sorted

    I tried to pass vectors between functions and i was having many problems doing so.

    after finding out how to do it by reference here; http://forums.devarticles.com/c-c-he...-c-150630.html

    i have started to cut down my program into functions
    Last edited by imhiya; March 15th, 2011 at 08:41 AM.

  4. #4
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Help please with getting my dijkstra's algorithm sorted

    Quote Originally Posted by imhiya View Post
    I tried to pass vectors between functions and i was having many problems doing so.
    What problems?
    Code:
    #include <vector>
    
    void vectorFunction(std::vector<int>& theVector)
    {
    }
    
    int main()
    {
        std::vector<int> vec;
        vectorFunction( vec );
    }
    I just passed vec by reference.

    Regards,

    Paul McKenzie

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)