Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle

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> (permalink)
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

Show key headers only | View raw

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

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