Thread: Help w/Dijkstra's algorithm

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Hampton, VA

    Help w/Dijkstra's algorithm

    Hi all,

    I'll say in advance that I'm only looking for suggestions, hints, etc. and some general answers to the question I'll ask to help me finish my assignment.

    Okay, here is an example we are following in class:
    class DistancePair{
    		DistancePair() : distance(0) {}
    		DistancePair( unsigned int ds, string& dt )
    		: distance( ds ), destination( dt ) {}
    		bool operator<( DistancePair& rhs ){ return distance < rhs.distance; }
    		unsigned int distance;
    		string destination;
    void dijkstra( graph& cityMap, string& start, map<string, unsigned int>& distances ){
    	priority_queue< vector<DistancePair>, greater<DistancePair> > que;
    	que.push( DistancePair( 0, start ) );
    	while( !que.empty() ){
    		int distance =;
    		string city =;
    		if( distances.count( city ) == 0 ){
    			distances[city] = distance;
    			map<string, unsigned int>::iterator start, stop;
    			start = cityMap[city].begin();
    			stop = cityMap[city].end();
    			for(; start != stop; ++start){
    				unsigned int destDistance = (*start).second;
    				string destCity = (*start).first;
    				que.push(DistancePair( distance + destDistance, destCity) );
    For my sake however, the above is hardly applicable.

    Here's how things are currently organized in my program:

    -The "paths" in my program are objects that contain two "coordinate" objects (each with x,y,z values)

    So they look like this respectively:
    class Coord{
        Coord( double x, double y, double z)
        : x_cord(x), y_cord(y), z_cord(z){}
        double x_cord, y_cord, z_cord;
    class Path{
        Path( Coord init, Coord term )
        : initial( init ), terminal( term ) {}
        Coord initial, terminal;
    Okay the above is what we're following in class, but I'm trying to figure out how to apply what I have to
    Dijkstra's algorithm.

    1) My Path objects are stored in a std::set because it was advantageous to not have redundant entries,
    and also it was nice to have the Path object itself be the "key". So in the above function dijkstra(),
    which argument does my std::set correlate to? ( cityMap or distances )?

    2) My guess is the answer to question 1 is "cityMap" but then what is distances?

    3) Also since my I don't have cityMap or distances, and my objects don't have a string name like the example,
    how might I handle those differences?

    Any help, suggestions and fingers pointed in the right direction are most appreciated!

    Thank You all in advance.
    Ubuntu Desktop
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Visalia, CA, USA
    I don't know how to answer this without committing the sin of doing a chunk of your homework for you. First off, why not make a class that has an overloaded == operator that compares the data. This would help seek out duplicates. Next off, if my class handles objects of a different type than your object if I wanted my object to interface with your object I'd either write code within my object to handle the task (or, and this is what I recommend you do) write a class that inherits my class that copes with your class. You could even write something that inherits from both classes. But again, I am only pitching ideas.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM