Hallo,
hab mir mal einen Dijkstra-Algorythmus zusammen gezimmert. Es kommt zwar eine NPE, aber ich glaube das ist nur nen "Flüchtigkeitsfehler". Um die NPE geht es mir aber auch gar nicht. Ich möchte eigentlich nur wissen, ob das Prinzip, nachdem ich vorgehen sinnvoll ist.
Ich habe einmal eine Methode die eine Liste zurückgibt, ind er jeweils der Kürzeste Weg zum angegebene Knoten ist. eine MEthode doe aus dieser Liste den Kürzesten Weg für den gesuchten Knoten gibt und eine Hilfmethode, die selbsterklärend ist.
Würd mich über Hilfe freuen.
Hier mal der Quellcode.
LG Kampfzwereg
hab mir mal einen Dijkstra-Algorythmus zusammen gezimmert. Es kommt zwar eine NPE, aber ich glaube das ist nur nen "Flüchtigkeitsfehler". Um die NPE geht es mir aber auch gar nicht. Ich möchte eigentlich nur wissen, ob das Prinzip, nachdem ich vorgehen sinnvoll ist.
Ich habe einmal eine Methode die eine Liste zurückgibt, ind er jeweils der Kürzeste Weg zum angegebene Knoten ist. eine MEthode doe aus dieser Liste den Kürzesten Weg für den gesuchten Knoten gibt und eine Hilfmethode, die selbsterklärend ist.
Würd mich über Hilfe freuen.
Hier mal der Quellcode.
Java:
public class DijkstraRechner {
public List berechneWegZuEinem(Graph pGraph, GraphNode pStart, GraphNode pZiel)
{
List wegZuZiel = new List();
List knoten = pGraph.getNodes();
int[] wegZuAllen = berechneWegZuAllen(pGraph, pStart);
knoten.toFirst();
int zaehler = 0;
while(knoten.hasAccess() && knoten.getObject() != pZiel)
{
knoten.next();
zaehler++;
}
wegZuZiel.append((GraphNode)knoten.getObject());
wegZuZiel.toFirst();
while(wegZuZiel.getObject() != pStart)
{
int temp = wegZuAllen[zaehler];
zaehler = temp;
int zaehler2 =0;
knoten.toFirst();
while(zaehler != zaehler2)
{
knoten.next();
zaehler2++;
}
wegZuZiel.insert((GraphNode)knoten.getObject());
wegZuZiel.toFirst();
}
return wegZuZiel;
}
private int[] berechneWegZuAllen(Graph pGraph, GraphNode pStart)
{
if(pStart == null)
{
int n=0;
int zaehler=0;
List knoten = pGraph.getNodes();
knoten.toFirst();
while(knoten.hasAccess())
{
zaehler++;
}
knoten.toFirst();
while(knoten.hasAccess() && knoten.getObject() != pStart)
{
n++;
}
int[] dist = new int[zaehler];
int[] pred = new int[zaehler];
boolean[] besucht = new boolean[zaehler];
for(int i=0;i<zaehler;i++)
{
dist[i]= Integer.MAX_VALUE;
}
dist[n] = 0;
for(int i=0; i<dist.length; i++)
{
int naechster = gibKleinstenUnbesuchtenKnoten(dist, besucht);
besucht[naechster] = true;
knoten.toFirst();
for(int j = 0; j< naechster;j++)
{
if(knoten.hasAccess())
{
knoten.next();
}
}
GraphNode tempNode = (GraphNode) knoten.getObject();
List nachbarn = pGraph.getNeighbours(tempNode);
nachbarn.toFirst();
int anzahlNachbarn=0;
while(nachbarn.hasAccess())
{
anzahlNachbarn++;
}
for(int k=0; k<anzahlNachbarn;k++)
{
int tempZaehler=0;
nachbarn.toFirst();
for(int l=0;l <= k;l++)
{
if(nachbarn.hasAccess())
{
nachbarn.next();
tempZaehler++;
}
}
GraphNode tempNode2 = (GraphNode) nachbarn.getObject();
int d = (int)dist[naechster] + (int)pGraph.getEdgeWeight(tempNode, tempNode2);
if(dist[tempZaehler] > d)
{
dist[tempZaehler] = d;
pred[tempZaehler] = naechster;
}
}
}
return pred;
}
else
{
System.out.println("Knoten existiert nicht");
return null;
}
}
private int gibKleinstenUnbesuchtenKnoten(int [] dist, boolean [] besucht)
{
int x = Integer.MAX_VALUE;
int y = -1;
for (int i=0; i<dist.length; i++)
{
if (!besucht[i] && dist[i]<x)
{
y = i;
x = dist[i];
}
}
return y;
}
}LG Kampfzwereg
