Thread: 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:

Code:

class DistancePair{

	public:
	
		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 = que.top().distance;
		string city = que.top().destination;
		que.pop();
		
		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:

Code:

class Coord{

  public:

    Coord( double x, double y, double z)
    : x_cord(x), y_cord(y), z_cord(z){}

  private:

    double x_cord, y_cord, z_cord;
};

class Path{

  public:

    Path( Coord init, Coord term )
    : initial( init ), terminal( term ) {}

  private:

    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.