Benutzer:Sandrine
Strategie:
Man entfernt alle markierten Nodes aus der NachbarListe und durchläuft diese Liste und guckt, welches die kürzeste Kante zu pNode hat.
public GraphNode gibNaechstenNachbarn(GraphWithViewer gwv, GraphNode pNode)
{
GraphNode ergebnis = null;
double gewicht;
List nachbarListe = gwv.getNeighbours(pNode);
// alle Nachbarn werden in die NachbarListe eingefügt
nachbarListe.toFirst();
while(nachbarListe.hasAccess())
{
GraphNode aktKn=(GraphNode)nachbarListe.getObject();
if(aktKn.isMarked())
// wenn ein Objekt der NachbarListe markiert ist, dann wird es entfernt.
{
nachbarListe.remove();
}
else{
nachbarListe.next();
}
}
nachbarListe.toFirst();
// das erste Objekt der nachbarListe wird als Ergebnis deklariert
// und das Gewicht der Kante von diesem Objekt zu pNode als Gewicht
ergebnis = (GraphNode)nachbarListe.getObject();
gewicht = gwv.getEdgeWeight(pNode, ergebnis);
nachbarListe.next();
while(nachbarListe.hasAccess())
{
GraphNode aktuellerNode = (GraphNode)nachbarListe.getObject();
double aktuellesGewicht = gwv.getEdgeWeight(pNode, aktuellerNode);
if(aktuellesGewicht<gewicht)
// wenn ein Gewicht einer Kante von einem Nachbarn zu pNode kleiner ist als das Gewicht,
// dann wird dieses das neue Gewicht und der Nachbar wird das Ergebnis
{
ergebnis = aktuellerNode;
gewicht = gwv.getEdgeWeight(pNode, aktuellerNode);
}
nachbarListe.next();
}
return ergebnis;
}