Class Dijkstra

java.lang.Object
  extended byAdjazenzliste
      extended byDijkstra

public class Dijkstra
extends Adjazenzliste

Diese Klasse stellt Routinen zur Verfügung, die Anhand einer Adjazenzliste den kürzesten Weg von einem Startknoten berechnet. Optional kann ein Zielknoten vorgegeben werden.


Field Summary
 
Fields inherited from class Adjazenzliste
adlist
 
Constructor Summary
Dijkstra()
          Konstruktor, der initiale Werte vergibt.
Dijkstra(Adjazenzliste al)
          Konstruktor, der initiale Werte vergibt und die Adjazenzliste übernimmt.
 
Method Summary
 int getCompareCounter()
          Gibt zurück, wie viele Vergleiche der Algorithmus bisher benötigt hat.
 Heap getHeap()
          Methode, die den Zugriff auf den Heap ermöglicht.
 Node getLastInspectedNode()
          Gibt den Knoten zurück, dessen Kanten zuletzt untersucht wurden.
 int[] getPredecessor()
          Liefert die Vorgängerliste.
 int getPredecessorLength()
          Gibt die Länger der Vorgängerliste zurück.
 long getUsedTime()
          Gibt die verbrauchte Zeit in Millisekunden an, die der letzte Algorithmusschritt benötigt hat.
 boolean heapIsEmpty()
          Methode, die prüft, ob der Heap leer ist.
 java.util.Vector shortestPath(GraphNode start, GraphNode end)
          Startet den Algorithmus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse GraphNode).
 java.util.Vector shortestPath(Node start, Node end)
          Startet den Algorithmus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse Node).
 java.util.Vector startShortestPathStepModus(GraphNode start, GraphNode end)
          Startet den Algorithmus im Step Modus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse GraphNode).
 java.util.Vector startShortestPathStepModus(Node start, Node end)
          Startet den Algorithmus im Step Modus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse GraphNode).
 java.util.Vector stepShortestPath()
          Führt einen Schritt im Algorithmus aus.
 void updateAdjazenzliste(Adjazenzliste al)
          Methode, die die Adjazenzliste neu zuordnet.
 
Methods inherited from class Adjazenzliste
add, add, add, add, contains, contains, contains, contains, find, getAdlist, getCost, getEdgesWithTail, getEdgesWithTail, getMaxNodeNumber, getNodeVector, main, ordnung, readFrom, remove, remove, remove, size, sortEdgeList, sortEdgeList, sortEdgeLists, toHtml, toString, writeAsText, writeTo
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

Dijkstra

public Dijkstra()
Konstruktor, der initiale Werte vergibt.


Dijkstra

public Dijkstra(Adjazenzliste al)
Konstruktor, der initiale Werte vergibt und die Adjazenzliste übernimmt.

Method Detail

heapIsEmpty

public boolean heapIsEmpty()
Methode, die prüft, ob der Heap leer ist.


updateAdjazenzliste

public void updateAdjazenzliste(Adjazenzliste al)
Methode, die die Adjazenzliste neu zuordnet.


shortestPath

public java.util.Vector shortestPath(GraphNode start,
                                     GraphNode end)
Startet den Algorithmus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse GraphNode). Dabei darf der Knoten end auch null sein. Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem Falle null.


shortestPath

public java.util.Vector shortestPath(Node start,
                                     Node end)
Startet den Algorithmus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse Node). Dabei darf der Knoten end auch null sein. Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem Falle null.


startShortestPathStepModus

public java.util.Vector startShortestPathStepModus(GraphNode start,
                                                   GraphNode end)
Startet den Algorithmus im Step Modus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse GraphNode). Dabei darf der Knoten end auch null sein. Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem Falle null.


startShortestPathStepModus

public java.util.Vector startShortestPathStepModus(Node start,
                                                   Node end)
Startet den Algorithmus im Step Modus, für die Berechnung eines kürzesten Weges von dem Knoten start nach end (beides Objekte der Klasse GraphNode). Dabei darf der Knoten end auch null sein. Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem Falle null. Es wird nur die Initialisierung des Algorithmus ausgeführt.


getHeap

public Heap getHeap()
Methode, die den Zugriff auf den Heap ermöglicht.


getPredecessor

public int[] getPredecessor()
Liefert die Vorgängerliste.


getPredecessorLength

public int getPredecessorLength()
Gibt die Länger der Vorgängerliste zurück.


getLastInspectedNode

public Node getLastInspectedNode()
Gibt den Knoten zurück, dessen Kanten zuletzt untersucht wurden. Dieser Knoten wurde im letzten Algorithmusschritt aus dem Heap genommen.


getUsedTime

public long getUsedTime()
Gibt die verbrauchte Zeit in Millisekunden an, die der letzte Algorithmusschritt benötigt hat. Dies kann der Ablauf des ganzen Algorithmus gewesen sein, oder aber ein einzelner Algorithmusschritt.


getCompareCounter

public int getCompareCounter()
Gibt zurück, wie viele Vergleiche der Algorithmus bisher benötigt hat.


stepShortestPath

public java.util.Vector stepShortestPath()
Führt einen Schritt im Algorithmus aus. Dabei werden die einzelnen Variablen, wie die Anzahl der Vergleiche oder die verbrauchte Zeit aktualisiert.