Dijkstra-Algorithmus-Variation in Javascript

[Ernst H. (Firma: Laboratorium_S1) (ernst_haft)]

Hallo.

In meinem Letzten Beitrag 
(Beitrag "Javascript Verkehrsleitsystem") wurde mir geraten, 
für das Finden des kürzesten Weges zwischen zwei Punkten den 
A*-Algorithmus zu verwenden.

Nach einigen Recherchen lernte ich jedoch den Dijkstra-Algorithmus 
kennen, der mir nicht nur verständlicher, sondern auch einfacher 
erscheint, da nicht berechnet werden muss, wie wahrscheinlich es ist, 
dass ein bestimmter Pfad eher zum Ziel führt als andere.

Ich fand nach einiger Suche Code für JavaScript, der Programmiersprache, 
in der ich den Algorithmus implementieren möchte, auf folgender Seite:
https://www.tutorialspoint.com/Dijkstra-s-algorithm-in-Javascript

Jedoch gibt dieser die kürzeste Entfernung zu allen weiteren Knoten von 
einem Startknoten aus an. Ich benötige jedoch zum einen die Entfernung 
zu einem bestimmten Knoten, zum anderen möchte ich wissen, welchen Pfad 
das Programm errechnet hat.

Wie müsste ich den Code umschreiben? Wird in der "while 
(!pq.isEmpty())"-Schleife geprüft, ob der Ziel-Knoten schon erreicht 
ist?

Zu Beginn des Programms würde ich ein Array initialisieren ("let pfad = 
[];"), welches ebenfalls ausgegeben wird und den "zu gehenden" Pfad 
angibt.

In welcher Schleife werden dann die Knoten des Pfades diesem Array 
hinzugefügt?

Verzeiht die etwas plumpe Grußformel und Verabschiedung. Was kreative 
Begrüßungen und Verabschiedungen angeht, bin ich (zum Glück?) kein 
Profi.

Viele Grüße und Dank für jede hilfreiche Antwort
Ernst

[Herbert B. (Gast)]

Ernst H. schrieb:
> Wie müsste ich den Code umschreiben? Wird in der "while
> (!pq.isEmpty())"-Schleife geprüft, ob der Ziel-Knoten schon erreicht
> ist?
https://de.wikipedia.org/wiki/Vorrangwarteschlange

[Sophie T. (sophie_t)]

1) Du prüfst einfach ab ob aus "pq" dein Zielknoten herausgenommen wird. 
In dem Moment kannst du den Algorithmus vorzeitig terminieren:

direkt nach der Zeile
let minNode = pq.dequeue();

machst du:

if minNode.node == "Zielknoten" { break; }


2) Um den Pfad zu rekonstruieren musst du nur "prev" nutzen.
prev speichert den Vorgängerknoten des kürzesten Pfades. Das heißt du 
fängst beim Zielknoten an prev auszuwerten und hangelst dich so 
rückwärts durch den kürzesten Pfad bis du irgendwann beim Startknoten 
angekommen bist.

Noch ein Hinweis. Dijkstra funktioniert nur mit nichtnegativen (>=0) 
Kantengewichten korrekt (liefert den kürzesten Pfad).

[Sophie T. (sophie_t)]

In Pseudocode könnte das so aussehen:

function reconstruct_path(prev: Array, Startknoten, Zielknoten) {
  let curNode = Zielknoten;
  let Pfad : Array = [Zielknoten];
  
  while curNode != Startknoten {
    //ist ein Vorgänger für diesen Knoten hinterlegt?
    //wenn nicht dann gibt es keinen Pfad vom Start- zum Zielknoten
    if curNode != null {
      curNode = prev[curNode];
      Pfad.push(curNode);
    } else {
      throw new Exception("Es gibt keinen Pfad vom Startknoten zum Zielknoten");
    }
  }
  
  //bei Bedarf den Pfad umdrehen
  return Pfad.reverseArray();
}

[Sophie T. (sophie_t)]

Theoretisch reicht es den else Zweig

} else {
      throw new Exception("Es gibt keinen Pfad vom Startknoten zum Zielknoten");
    }

genau einmal für den Zielknoten am Anfang (vor der Schleife) 
auszuführen. Denn wenn dieser Knoten einen Vorgänger hat muss der 
Algorithmus vom Startknoten aus irgendwann dort hingekommen sein. Es 
gibt also einen Pfad. So kann man den Algorithmus etwas optimieren...