Wie linkedlist für Djikstra nutzen?

[Binary.Coder]

Hallo zusammen,

ich möchte gerne den Dijkstra-Algorithmus Dijkstra-Algorithmus ? Wikipedia nachprogrammieren.

Als Datentyp würde ich gerne eine linked list benutzen.
Bisher habe ich die immer selbstgeschrieben aber die gibt es auch in der API nehme ich mal schwer an.

Frage mich nur wie ich dann mehrere Vorgänger definieren soll.

Habt ihr einen Tipp?

Vielen Dank schonmal!

Edit: Das gleiche Problem mit mehreren Zeigern habe ich auch beim next Zeiger

 

[Landei]

Das geht nicht. Drei Lösungsmöglichkeiten:
- du definierst eine Klasse für die Kanten und packst diese Objekte in eine Liste oder ein Set
- du definierst eine Klasse für die Knoten, die intern eine Liste von Nachbarknoten enthält, und packst diese Objekte in eine Liste oder ein Set
- Du hast eine Map von einem Knoten auf eine Liste von Nachbarknoten

Die Implementierung auf Literate Programs realisiert Variante 1 und 2, hat also eigene Kanten- und Knotenklassen.

 

[Binary.Coder]

Vielen Dank.
Habe es ähnlich wie bei deinem Link realisiert.

Peinliche Frage: Ich habe eine Klasse für Knoten und eine für Kanten.
Muss ich die dann extenden oder importieren?

 

[Marcinek]

Du solltest entweder einen Knoten oder die Kanten im Modell aufnehmen. Beides macht keinen Sinn.

Du würdest einen Knoten so implementieren

class Knoten {
    Object meinObjekt = null;

    list<knoten> meineNachbarn = ...

}

 

[Binary.Coder]

Danke aber so war das nicht gemeint.

Schau, ich habe jetzt drei Klassen.

Knoten, Kanten und den Dijkstra.

Knoten und Kanten greifen gegenseitig aufeinander zu und der Dijkstra greift auf beide zu.

Wie soll ich die verbinden, damit es so wäre als wären sie alle in einer Klasse.

Eine idee wäre import.
Ich importiere in der Klasse Knoten die Kanten und andersrum und beim Dijkstra dann beide.
Wäre das richtig? Oder muss ich extenden? (hab dazu schon gegooglt bin aber noch noch unschlüssig).

 

[Landei]

Du solltest entweder einen Knoten oder die Kanten im Modell aufnehmen. Beides macht keinen Sinn.

Warum machen sie es dann hier so? Dijkstra's algorithm (Java) - LiteratePrograms

Könntest du diese Version verbessern, indem du Kanten oder Knoten wegläßt?

 

[Landei]

Danke aber so war das nicht gemeint.

Schau, ich habe jetzt drei Klassen.

Knoten, Kanten und den Dijkstra.

Knoten und Kanten greifen gegenseitig aufeinander zu und der Dijkstra greift auf beide zu.

Wie soll ich die verbinden, damit es so wäre als wären sie alle in einer Klasse.

Eine idee wäre import.
Ich importiere in der Klasse Knoten die Kanten und andersrum und beim Dijkstra dann beide.
Wäre das richtig? Oder muss ich extenden? (hab dazu schon gegooglt bin aber noch noch unschlüssig).

Importieren ist richtig.

Die Entscheidung ist ganz einfach: Extenden nur dann, wenn man eine "ist ein"-Beziehung hat. Ist ein Knoten eine Kante? Nein. Ist eine Kante ein Knoten? Nein. Ist eines von beiden ein Dijkstra-Algorithmus - oder umgekehrt? Nein. Also nicht extenden.