Path: csiph.com!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!.POSTED.xdsl-89-1-55-60.netcologne.de!not-for-mail
From: Patrick Roemer <sangamon@netcologne.de>
Newsgroups: de.comp.lang.java
Subject: Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle
Date: Fri, 5 Jan 2018 12:57:49 +0100
Organization: news.netcologne.de
Distribution: world
Message-ID: <p2np7t$hcj$1@newsreader4.netcologne.de>
References: <fb77giFjev3U1@mid.individual.net> <fb7rb9Fo3tqU1@mid.individual.net> <fb949dF28mqU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 5 Jan 2018 11:57:49 +0000 (UTC)
Injection-Info: newsreader4.netcologne.de; posting-host="xdsl-89-1-55-60.netcologne.de:89.1.55.60"; logging-data="17811"; mail-complaints-to="abuse@netcologne.de"
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.24) Gecko/20100411 Thunderbird/2.0.0.24 Mnenhy/0.7.6.0
In-Reply-To: <fb949dF28mqU1@mid.individual.net>
Content-Language: en-US
Xref: csiph.com de.comp.lang.java:13160

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