Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Dijkstra-Routingnetz: Alle Knoten finden die max m Meter entfernt sind
C#SHARP
myCSharp.de - Member



Dabei seit:
Beiträge: 40

Themenstarter:

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

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
jaensen
myCSharp.de - Experte

Avatar #avatar-2657.png


Dabei seit:
Beiträge: 2.760
Herkunft: München

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
malignate
myCSharp.de - Member

Avatar #avatar-3206.png


Dabei seit:
Beiträge: 742

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
C#SHARP
myCSharp.de - Member



Dabei seit:
Beiträge: 40

Themenstarter:

beantworten | zitieren | melden

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

@malignate Weglinie ....
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
C#SHARP
myCSharp.de - Member



Dabei seit:
Beiträge: 40

Themenstarter:

beantworten | zitieren | melden

@all: werde das Rad nicht neu erfinden und überlasse die Berechnung ESRI (GIS Software) ;)
private Nachricht | Beiträge des Benutzers