Najkrótsza ścieżka w grafie - dodanie jednej metody

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.

Po pierwsze,

double Node::getEuclideanDistance(const Node &target) const
  {
   return hypot(getCoordinates().getX() - target.getCoordinates().getX(),getCoordinates().getY() - target.getCoordinates().getY());
  }

Po drugie, nie jesteś w stanie napisać pętli czy nie znasz algorytmu znajdowania minimum?

_13th_Dragon napisał(a):

Po drugie, nie jesteś w stanie napisać pętli czy nie znasz algorytmu znajdowania minimum?

Potrafię napisać to w C. Nie potrafię napisać tutaj pętli (C++) - kombinowałem z tym trochę ale nic nie wyszło.

bool haveNothing=true;
double bestDistance=0;
map<string,Node>::iterator best;
for(map<string,Node>::iterator i=m_nodes.begin();i!=m_nodes.end();++i)
  {
   Node &n=i->second;
   double distance=hypot(n.getCoordinates().getX()-n.getCoordinates().getY()-y);
   if((haveNothing)||(bestDistance>distance))
     {
      bestDistance=distance;
      haveNothing=false;
      best=i;
     }
  }
if(haveNothing) throw "Nie znaleziono";
string label=best->first;
Node &node=best->second;