Witam serdecznie wszystkich,
Mam pewien problem związany z kodem programu realizującego wyszukiwanie najkrótszej/optymalnej ścieżki w grafie.
Otóż potrzebuję jego do bardziej zaawansowanego programu. Wszystkie pliki w załączeniu. Jest tam także przykładowa "mapa" (na bazie Open Street Map) Monako.
Po rozpakowaniu archiwum program możemy skompilować następująco:
g++ main.cpp graph.cpp -o main
Przykładowy wycinek z pliku grafu/mapy to:
17801
21911863 43.7370125 7.422028
21911883 43.7371175 7.4229093
21911886 43.7372399 7.4234985
21911888 43.7375272 7.425191
21911894 43.7377782 7.4259476
21911901 43.7377621 7.4267099
21911908 43.7381906 7.426961
21911954 43.7383862 7.4269064
21911969 43.7384518 7.426836
...
18913
21912089 1079750744 0.75
2104793864 21912089 0.75
1110560507 2104793864 0.75
21912093 1110560507 0.75
21912095 21912093 0.75
1079751630 21912095 0.75
21912097 1079751630 0.75
...
Pierwsza wartość w tym pliku (pierwsza linijka) to ilość wierzchołków. Po niej w kolejnych liniach są wypisywane dane kolejnych wierzchołków (w kolejności: etykieta (tj. numer), współrzędna x, współrzędna y).
Następnie po wszystkich wierzchołkach znajdziemy zapisaną ilość krawędzi w grafie (tutaj 18913). Po niej wypisywane są krawędzie w formacie (nazwa wierzchołka startowego, nazwa wierzchołka końcowego, waga).
Za wczytywanie odpowiada poniższy kod:
DirectedWeightedGraph::DirectedWeightedGraph(istream &in)
{
// Format pliku wejciowego:
//
// n
// lbl x y
// ...
// m
// lbl1 lbl2 weight
// ...
int n;
in >> n;
for (int i=0; i<n; ++i) {
string label;
double x, y;
in >> label >> x >> y;
m_nodes.insert(pair<string,Node>(label, Node(label, Coordinates(x,y))));
}
int m;
in >> m;
for (int i=0; i<m; ++i) {
string label;
double weight;
in >> label;
map<string,Node>::iterator iSourceNode = m_nodes.find(label);
in >> label;
map<string,Node>::iterator iTargetNode = m_nodes.find(label);
in >> weight;
iSourceNode->second.addAdjacentNode(iTargetNode->second, weight);
}
}
Przejdźmy teraz do sedna galimatiasu. Mam współrzędną x i współrzędną y jakiegoś punktu (są to double). Potrzebuję metody, która przeleci po wszystkich wierzchołkach w grafie i zwróci etykietę (tj. tutaj numer) wierzchołka, który znajduje się najbliżej tego punktu o podanych współrzędnych.
Odległość mierzona w sensie odległości euklidesowej:
double Node::getEuclideanDistance(const Node &target) const
{
double dx = getCoordinates().getX() - target.getCoordinates().getX();
double dy = getCoordinates().getY() - target.getCoordinates().getY();
return sqrt(dx*dx + dy*dy);
}
Ktoś mógłby jakoś pomóc coś takiego ugryźć?
// PS. Zapomniałem dodać - kod w załączniku testowany jedynie na Linuxie.