000
19.02.2007, 18:13 Uhr
mike
Pinguinhüpfer
(Operator)
|
Hallo
Ich will den kürzesten Pfad zwischen 2 Punkten finden - das ist ein altbekanntes Problem daher habe ich Dijkstra genommen.
| C++: |
#include <iostream>
#include <map>
#include <string>
#include <queue>
class Destination {
public:
double distance;
std::string destination; // need to be public below
Destination (std::string dt, double ds) : distance(ds), destination(dt) {}
bool operator< (const Destination & right) const {
return distance > right.distance;
} //reversed so smaller come first in priority_queue
};
typedef std::map<std::string, double> vDistanceMap;
typedef std::map<std::string, vDistanceMap> vGraphMap;
vGraphMap myGraphVec_;
void Dijkstra(vGraphMap& cityMap, std::string start, vDistanceMap & travelCosts)
// Dijkstra's single source shortest path algorithm
{ // keep a priority queue of distances to cities
std::priority_queue <Destination> que;
que.push (Destination(start, 0));
// while queue not empty
while (!que.empty()) {
// remove top entry from queue
std::string newCity = que.top().destination;
double cost = que.top().distance;
que.pop();
// if so far unvisited,
if(travelCosts.count(newCity) == 0) {
// visit it now
travelCosts[newCity] = cost;
// add reachable cities to list
vDistanceMap::iterator start = myGraphVec_[newCity].begin();
vDistanceMap::iterator stop = myGraphVec_[newCity].end();
for (; start != stop; ++start) {
std::string destCity = (*start).first;
double destDistance = (*start).second;
que.push(Destination(destCity, cost + destDistance));
}
}
}
}
int main (int argc, char * const argv[]) {
myGraphVec_["Ort1"]["Ort2"] = 5;
myGraphVec_["Ort2"]["Ort3"] = 5;
myGraphVec_["Ort1"]["Ort3"] = 15;
vDistanceMap costs;
Dijkstra( myGraphVec_, "Ort1" , costs );
vDistanceMap::iterator it = costs.begin(), stop = costs.end();
for( ; it != stop ; it++ )
std::cout << "from " << "Ort1" <<" to " << it->first << " costs " << it->second << std::endl;
return 0;
}
|
Nun gibt er korrekt aus dass zwischen Ort1 und Ort3 der kürzeste Weg 10 ist. Mein Problem ist nun: Wie kann ich speichern wie der kürzeste Weg verläuft? Also in meinem Beispiel Ort1 - Ort 2 - Ort3
Hab schon die wildestens Konstrukte probiert - aber ich komme nicht dahinter 
Danke im Voraus
lg
--
Dieser Post wurde am 19.02.2007 um 18:15 Uhr von mike editiert. |
