/*
* YAV (Yet another Visualiser)
* (c) 2004 by Robin Quast
* Version 1.0 (04.03.2004)
*
* erstellt im Rahmen der Diplomarbeit
* "Theorie und Java- Realisierung
* ausgewählter Algorithmen zur
* Bestimmung kürzester Wege in Graphen"
*
* betreut durch Prof. Dr. Lenze
* an der Fachhochschule Dortmund
* im SS 2003/ WS 2003/2004
*
* @(#)Dijkstra.java 1.1 04/03/09
*/
import java.*;
import java.util.Vector;
import java.util.Enumeration;
import java.io.*;
import java.util.Calendar;
/** 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.
*/
public class Dijkstra
extends Adjazenzliste {
int knotenanzahl = 0;
int[] vorgaenger = new int[knotenanzahl+1];
Vector knotenvektor = new Vector();
Heap h = new Heap();
Enumeration heap_enum = knotenvektor.elements();
Node source = new Node();
Node destination = new Node();
Node last_inspected_node;
long used_time;
int compare_counter=0;
/** Konstruktor, der initiale Werte vergibt.
*/
public Dijkstra() {
super();
last_inspected_node = new Node();
}
/** Konstruktor, der initiale Werte vergibt und die Adjazenzliste übernimmt.
*/
public Dijkstra(Adjazenzliste al) {
super();
adlist = al.getAdlist();
last_inspected_node = new Node();
}
/** Methode, die prüft, ob der Heap leer ist.
*/
public boolean heapIsEmpty() {
return h.isEmpty();
}
/** Methode, die die Adjazenzliste neu zuordnet.
*/
public void updateAdjazenzliste(Adjazenzliste al) {
adlist = al.getAdlist();
}
/** Startet den Algorithmus, für die Berechnung eines kürzesten Weges
* von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der
* Klasse GraphNode). Dabei darf der Knoten <i>end</I> auch null sein.
* Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem
* Falle <I>null</I>.
*/
public Vector shortestPath (GraphNode start,GraphNode end) {
if (start==null) return null;
if (end==null) return shortestPath(start.getNode(),null);
return shortestPath(start.getNode(),end.getNode());
}
/** Startet den Algorithmus, für die Berechnung eines kürzesten Weges
* von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der
* Klasse Node). Dabei darf der Knoten <i>end</I> auch null sein.
* Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem
* Falle <I>null</I>.
*/
public Vector shortestPath (Node start,Node end) {
source = new Node(start);
if (end!=null) destination = new Node(end);
else destination = null;
compare_counter=0;
last_inspected_node = new Node();
used_time=getTimeInMillis();
//if (!(source==null) || (destination==null)) {
if (!(source==null)) {
initialiseDijkstra();
// ermittle den kürzesten Weg von start Knoten
while (!(h.isEmpty())) {
HeapElement min=h.findAndRemoveMin();
Vector kanten = getEdgesWithTail(min.getNode());
if (!(min.getKey()==Integer.MAX_VALUE)) {
Enumeration kanten_enum = kanten.elements();
while (kanten_enum.hasMoreElements()) {
Object tmp_element=kanten_enum.nextElement();
Edge tmp_edge = (Edge) tmp_element; // Kante hat den Knoten tail = min.getNode() !
Node head = tmp_edge.getHead();
int cost = min.getKey()+tmp_edge.getCost();
compare_counter++;
if (cost<h.getCost(head)) {
h.setCost(head,cost);
vorgaenger[head.getValue()]=min.getNodeValue();
}
}
//compare_counter++;
}
}
}
used_time=getTimeInMillis()-used_time;
return getShortestPathEdgeVector();
}
/** Liefert die Zeit in Millisekunden, damit die Dauer der letzten
* Algorithmusaktion gemessen werden kann.
*/
private long getTimeInMillis() {
Calendar cal = Calendar.getInstance();
return cal.getTimeInMillis();
}
/** Startet den Algorithmus im Step Modus, für die Berechnung eines kürzesten Weges
* von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der
* Klasse GraphNode). Dabei darf der Knoten <i>end</I> auch null sein.
* Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem
* Falle <I>null</I>.
*/
public Vector startShortestPathStepModus (GraphNode start,GraphNode end) {
if (start==null) return null;
if (end==null) return startShortestPathStepModus(start.getNode(),null);
return startShortestPathStepModus(start.getNode(),end.getNode());
}
/** Startet den Algorithmus im Step Modus, für die Berechnung eines kürzesten Weges
* von dem Knoten <i>start</I> nach <i>end</I> (beides Objekte der
* Klasse GraphNode). Dabei darf der Knoten <i>end</I> auch null sein.
* Der Startknoten darf nicht null sein. Das Ergebnis wäre in diesem
* Falle <I>null</I>. Es wird nur die Initialisierung des Algorithmus ausgeführt.
*/
public Vector startShortestPathStepModus (Node start,Node end) {
source = new Node(start);
if (end!=null) destination = new Node(end);
else destination=null;
last_inspected_node = new Node();
compare_counter=0;
used_time=getTimeInMillis();
if (!(source==null)) {
initialiseDijkstra();
}
used_time=getTimeInMillis()-used_time;
return getShortestPathEdgeVector();
}
/** Methode, die den Zugriff auf den Heap ermöglicht.
*/
public Heap getHeap() {
return h;
}
/** Liefert die Vorgängerliste.
*/
public int[] getPredecessor() {
return vorgaenger;
}
/** Gibt die Länger der Vorgängerliste zurück.
*/
public int getPredecessorLength() {
return vorgaenger.length;
}
/** Gibt den Knoten zurück, dessen Kanten zuletzt untersucht wurden. Dieser
* Knoten wurde im letzten Algorithmusschritt aus dem Heap genommen.
*/
public Node getLastInspectedNode() {
return last_inspected_node;
}
/** 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.
*/
public long getUsedTime(){
return used_time;
}
/** Gibt zurück, wie viele Vergleiche der Algorithmus bisher benötigt hat.
*/
public int getCompareCounter() {
int rc=compare_counter;
return rc;
}
/** Führt einen Schritt im Algorithmus aus. Dabei werden die einzelnen
* Variablen, wie die Anzahl der Vergleiche oder die verbrauchte Zeit
* aktualisiert.
*/
public Vector stepShortestPath (){
if (!(h.isEmpty())) {
used_time=getTimeInMillis();
HeapElement min=h.findAndRemoveMin();
last_inspected_node = new Node(min.getNode());
if (!(min.getKey()==Integer.MAX_VALUE)) {
Vector kanten = getEdgesWithTail(min.getNode());
Enumeration kanten_enum = kanten.elements();
while (kanten_enum.hasMoreElements()) {
Object tmp_element=kanten_enum.nextElement();
Edge tmp_edge = (Edge) tmp_element; // Kante hat den Knoten tail = min.getNode() !
Node head = tmp_edge.getHead();
int cost = min.getKey()+tmp_edge.getCost();
compare_counter++;
if (cost<h.getCost(head)) {
h.setCost(head,cost);
vorgaenger[head.getValue()]=min.getNodeValue();
}
}
}
used_time=getTimeInMillis()-used_time;
//compare_counter++;
}
return getShortestPathEdgeVector();
}
/** Diese Methode gibt einen Vector zurück, der die Kanten des kürzesten Weges,
* bzgl. der Vorganben enthält.
*/
private Vector getShortestPathEdgeVector () {
Vector kuerzester_weg = new Vector();
if (source==null) return kuerzester_weg;
if (destination==null) {
return getShortestPathEdgeVectorForSource();
}
if (destination.getValue()==-1) {
return getShortestPathEdgeVectorForSource();
}
// hier ist source!=null und destination !=null
// kürzesten Weg für die Ausgabe aufbereiten
int i_knoten = destination.getValue();
kuerzester_weg.addAll(getShortestPathEdgeVectorForDestination(i_knoten));
return kuerzester_weg;
}
/** Wurde bei der kürzesten Wege- Berechnung kein Zielknoten vorgegeben
* wird diese Routine die kürzesten Wege zu allen Knoten zurückgeben.
*/
private Vector getShortestPathEdgeVectorForSource() {
Vector kuerzester_weg = new Vector();
int maxnnum = getMaxNodeNumber();
for (int i=0;i<maxnnum+1;i++) {
kuerzester_weg.addAll(getShortestPathEdgeVectorForDestination(i));
}
return kuerzester_weg;
}
/** Gibt den kürzesten Weg von <i>source</I> nach <i>node</I> zurück.
*/
private Vector getShortestPathEdgeVectorForDestination(int node) {
Vector kw=new Vector();
while (node!=source.getValue() && vorgaenger[node]!=-1) {
Edge tmp_e=find(vorgaenger[node],node);
if (tmp_e!=null) kw.add(tmp_e);
node=vorgaenger[node];
}
return kw;
}
/** Initialisiert die Algorithmuseinstellungen. Z.B. leeren des Heaps,
* setzen der Knotenliste,...
*/
private void initialiseDijkstra() {
// variablen initialisieren
knotenanzahl = getMaxNodeNumber();
vorgaenger= new int[knotenanzahl+1];
for (int i=0; i<knotenanzahl+1;i++) vorgaenger[i]=-1;
knotenvektor = getNodeVector();
h = new Heap();
heap_enum = knotenvektor.elements();
// Vorgaenger der Knoten und heap initialisieren
while (heap_enum.hasMoreElements()) {
Object tmp_element=heap_enum.nextElement();
Node tmp_node = (Node) tmp_element;
// Knoten zum heap hinzufügen
if (tmp_node.equal(source)) h.add(new HeapElement(tmp_node,0)); // der kürzeste Weg vom Startnoten zu sich selber ist 0
else h.add(new HeapElement(tmp_node,Integer.MAX_VALUE));// Integer.MAX_VALUE bedeutet hier, dass der Weg zu diesem Element noch nicht berechnet wurde, bzw. es wurde noch kein Weg gefunden, unter Umständen gibt es auch zu diesem Knoten keinen Weg
}
}
}
|