Dijakstra: Ist dieser Algo richtig notiert?
-
Hallo Forum,
ich möchte den Dijakstra Algo implementieren und habe im Internet dazu gegoogelt.
http://algorithmus_von_dijkstra.know-library.net/Hier geht es darum den kürzesten Weg zw Knoten s und e zu finden:
* Setze i = 0;
* Setze s als Startgraph T und nummeriere s mit i (= 0);
* Solange T noch nicht e enthält,
o Erhöhe i um 1;
o suche eine Kante minimalen Gewichts, die einen Knoten, der nicht in T ist, mit T verbindet und
o füge diese Kante und den somit verbundenen Knoten v zu T hinzu;
o Nummeriere v mit i;
* Laufe von e anfangend zurück zu s, indem als nächster Knoten stets der Knoten mit kleinster Nummerierung gewählt wird;So ist der Algo doch falsch? Nehmen wir an wir hätten einen Kreis mit 6 Knoten. Einen Knoten nennen wir s. Wir setzen das Gewicht der Kante zum linken Nachbarn zu 2. Von diesem aus sei der linke Nachbar e. Alle 4 restlichen Kanten haben das Gewicht 1. Dieser Algo würde doch zuerst alle Kanten mit 1 dem Graphen T hinzufügen und dann abbrechen wenn e erreicht sei. (Er würde den rechten Weg von s aus gehen. Länge: 4) Auf dem linken Weg würde er aber nur eine Länge von 3 haben.
-
Ja, ist falsch. f'`8k
Bye, TGGC (\-/ returns)
-
Hab den Leuten den Fehler im Forum mitgeteilt.
