Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: "Christian H. Kuhn" <qno-news@qno.de>
Newsgroups: de.comp.lang.java
Subject: Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle
Date: Fri, 5 Jan 2018 12:02:04 +0100
Lines: 34
Message-ID: <fb949dF28mqU1@mid.individual.net>
References: <fb77giFjev3U1@mid.individual.net> <fb7rb9Fo3tqU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Trace: individual.net b0HNFwS4M72Mg9WB94mhaQfQx4Q5iRQJdmok4ixDgcBEjEF0c=
Cancel-Lock: sha1:y+FN4rxUnQvQr8mN1MfQTVYFJVk=
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.5.2
In-Reply-To: <fb7rb9Fo3tqU1@mid.individual.net>
Xref: csiph.com de.comp.lang.java:13159

Bei mir hat sich die Verwirrung gelegt. Daher die Doppel-Ingrid.

Am 05.01.2018 um 00:23 schrieb Christian H. Kuhn:
> Ich bin mir nicht sicher, ob ich genügend Verwirrung gestiftet habe.
> Also mache ich mal die Ingrid:
> 
> Am 04.01.2018 um 18:44 schrieb Christian H. Kuhn:
>> TreeMap<Knoten, Knoten> nichtBesuchteKnoten;
>> TreeMap<Double, Knoten> warteSchlange;

Map<Knoten, Knoten> besuchteKnoten;

Da gehts schon los: Ich wollte (zu Recht) den Graphen nicht vorher
komplett berechnen und habe dabei den Überblick verloren. Ich glaubte,
nichtBesuchteKnoten und warteSchlange seien beides die
Prioritätswarteschlange. Sind sie nicht. besuchteKnoten und
nichtBesuchteKnoten bilden gemeinsam den Graphen, warteSchlange die
Warteschlange. Nachdem das klar war:

TreeMap<Knoten, Knoten> graph;
PriorityQueue<Knoten> warteSchlange;

Zum anderen war mir nicht an jeder Stelle klar, dass beide Strukturen
nicht unabhängige Elemente, sondern Zeiger auf das jeweils gleiche
Element erhalten.

Jetzt habe ich eine saubere Trennung von Graph und Warteschlange sowie
einige unnötige remove-add-Kombinationen entfernt, das hat der Laufzeit
gut getan. Dem Code und meinem Hirn auch :-)

lg
QNo