Halli hallo;
habe ein Problem bei einer in Pascal zu lösenden Aufgabe: Ich soll den Floyd-Warshall-Algorithmus (zur Berechnung der kürzesten Wege) implementieren und danach alle besuchten Knoten auf jedem Weg ausgeben.
Mein Graph ist folgendermaßen definiert:
type pvertex=^vertex;
pkanten=^kante;
vertex= record name: integer;
vkanten: pkanten;
next: pvertex;
end;
kante=record ziel:stuck_out_tongue:vertex;
gewicht:float;
next:stuck_out_tongue:kanten;
end;
matrix=array[1…n,1…n] of integer;
Also sind alle Knoten in einer Liste gespeichert mit dem Namen, einer Liste von den vom Knoten ausgehenden Kanten sowie dem Zeiger auf den nächsten Knoten. Der Graph wäre dementsprechend ein pvertex (Pointer auf den ersten Knoten).
Nun mein Problem: Beim Floyd-Warshall-Algorithmus muss ich jetzt ja eigentlich immer neue Knoten hinzunehmen, um zu überprüfen, ob sich Aktualisierungen in Bezug auf die kürzesten Wege ergeben, allerdings habe ich die Folgeknoten ja nicht im Knoten selbst gespeichert und muss alle Kanten durchtesten, ob der jeweilige Knoten tatsächlich ein Folgeknoten ist; daraus ergibt sich allein für diesen Schritt eine Komplexität von m*m! (m ist die Gesamtanzahl der Kanten), darum wollte ich fragen, ob jemand eine effektivere Idee hat.
mfG