# Thread: Help w/Dijkstra's algorithm

1. ## 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.

2. 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