nicht angemeldet
die laufzeit ist doch höher als vermutet, mein problem ist eigentlich:
gegeben: Graph G = (V,E), Startknoten S aus V und die Anzahl der zugehenden Schritte T
und ich möchte mir nun alle Knoten speichern, die ich von Knoten aus S innerhalb von T schritten erreichen kann und auch die dazugehörigen kantengewichte. außerdem hat G zykel.
weiß eventuell jemand, wie man so etwas machen kann, ohne dabei massig laufzeit zu verbrauchen?
Ah, eine schon viel bessere Beschreibung.
Ja, ich würde sagen, das geht wesentlich besser. An deiner Stelle würde ich mich an Dijkstra orientieren. Der berechnet in einem Graphen von einem Startknoten aus für jeden Knoten die geringste Distanz. Etwas angepasst kann man sogar mit vergleichsweise wenig Aufwand eine "Tabelle" anlege, über die man später sehr schnell den kürzsten Weg von jedem Knoten zu jedem anderen Knoten finden kann.
Guck dir also mal an, wie man Dijkstra effizient implementiert (insbesondere die Datenstrukturen), dann kriegst du das, was du willst sicherlich in _wesentlich_ geringerer Laufzeitkomplexität leicht über O(n*log(n)) hin.
MudGuard