Dijkstra-Routingnetz: Alle Knoten finden die max m Meter entfernt sind

Guten Tag,

hat jemand eine gute Idee, wie man folgendes Problem effizient löst?

Gegeben ist ein beliebiger Knoten eines Dijkstra-Routingnetzes. Von dort ausgehend sollen nun alle möglichen Knoten gefunden werden, die max m Meter vom Startknoten entfernt sind.

Danke

Servus,

klingt so als ob Du dafür den Dijkstra-Algorithmus nicht benötigen würdest da du ja keine Pfade zwischen Knoten finden möchtest. Das sollte mit einer einfachen Tiefensuche machbar sein in dem Du einfach bei jedem Schritt die nächste Kantenlänge addierst und prüfst ob sie noch innerhalb der max. zulässigen entfernung ist oder nicht.

Luftlinie oder Weglinie? Bei Luftlinie kannst du alternativ ein Quadtree oder so aufbauen, falls es sehr viele Knoten sind.

Bei der Weglinie wirst du wohl eine Tiefensuche machen müssen. Wichtig dabei, dass du Zyklen ignoriert.

@jaensen Danke für den Tipp mit der Tiefensuche!

@malignate Weglinie ....

Hallo C#SHARP,

aus meiner Sicht eher ein Fall für Breitensuche.

Und der Dijkstra-Algorithmus ist keine schlechte Basis dafür, denn mit diesem kann man verhindern, dass Knoten, zu denen es mehrere (verschiedene lange) Pfade gibt, unnötig mehrfach besucht werden.

herbivore

@all: werde das Rad nicht neu erfinden und überlasse die Berechnung ESRI (GIS Software) 😉