پياده سازي الگوريتم Dijkstra

آموزش کامپيوتر :: آموزش شبکه و امنيت شبکه

موضوع: پياده سازي الگوريتم Dijkstra

#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef map > graph;

class DistancePair
{
public:

DistancePair(unsigned int ds, string &dt)
: distance(ds), destination(dt)
{
}

bool operator>( const DistancePair &right ) const
{
return distance > right.distance;
}

string getDestination() const
{
return destination;
}

unsigned int getDistance() const
{
return distance;
}

private:
unsigned int distance;
string destination;
};

void dijkstra(graph &cityMap, string start,
map &distances)
{
priority_queue,
greater > que;
que.push(DistancePair(0,start));
while( !que.empty() ) {
int distance = que.top().getDistance();
string city = que.top().getDestination();
que.pop();
if( distances.count(city) == 0 ) {
distances[city] = distance;
map::iterator start, stop;
start = cityMap[city].begin();
stop = cityMap[city].end();
while( start != stop ) {
unsigned int destDistance = (*start).second;
string destCity = (*start).first;
que.push(DistancePair(distance + destDistance, destCity));
start++;
}
}
}

}

void buildCityMap(graph &cityMap) {
cityMap["A"]["B"] = 7;
cityMap["A"]["C"] = 4;
cityMap["A"]["D"] = 6;
cityMap["A"]["E"] = 1;
cityMap["C"]["B"] = 2;
cityMap["C"]["D"] = 5;
cityMap["D"]["B"] = 3;
cityMap["E"]["D"] = 1;

}

int main()
{
graph cityMap;
buildCityMap(cityMap);
map distances;
dijkstra(cityMap, "A", distances);
map::iterator start, stop;
start = distances.begin();
stop = distances.end();
while( start != stop ) {
cout << (*start).first << " " << (*start).second << endl;
start++;
}
getchar();

}

مطلب بعدی :: مطلب قبلی