Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle

From	Patrick Roemer <sangamon@netcologne.de>
Newsgroups	de.comp.lang.java
Subject	Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle
Date	2018-01-05 12:57 +0100
Organization	news.netcologne.de
Message-ID	<p2np7t$hcj$1@newsreader4.netcologne.de> (permalink)
References	<fb77giFjev3U1@mid.individual.net> <fb7rb9Fo3tqU1@mid.individual.net> <fb949dF28mqU1@mid.individual.net>

Show all headers | View raw

Responding to Christian H. Kuhn:

Ich habe dieses mehrteilige Epos nur überflogen, kann also gut sein,
dass ich was übersehen und/oder falsch verstanden habe...

> TreeMap<Knoten, Knoten> graph;

Was soll das denn darstellen?

Die Kanten doch wohl eher nicht, oder hat jeder Knoten nur eine
ausgehende Kante?

Die Menge aller Knoten? Da gibt's mit Set einen passenderen Typ.

> PriorityQueue<Knoten> warteSchlange;

Mit einer PriorityQueue hast Du aber doch kein gezieltes #remove()...?
Mit unveränderlichen Knoten wahrscheinlich nicht dramatisch - man
bekommt halt Duplikate, aber da eh nur der Eintrag mit der kürzesten
Distanz interessiert, stören die nicht, abgesehen davon, dass sie
Speicher fressen. Aber es klang so, als ob Deine Knoten mutable seien,
und dass Du ein O(n)-Traversal zwecks Removal vermeiden wolltest. Wie
passt das denn zusammen?

Viele Grüße,
Patrick

Back to de.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-04 18:44 +0100
  Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-05 00:23 +0100
    Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-05 12:02 +0100
      Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle Patrick Roemer <sangamon@netcologne.de> - 2018-01-05 12:57 +0100
        Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-07 20:57 +0100

csiph-web