# Dijkstra Algorythmus



## Kampfzwereg (9. Jun 2012)

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.



```
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


----------



## greatergood (10. Jun 2012)

Hi,

Auf den ersten Blick erscheint das alles etwas groß, um lediglich den Dijkstra Algorithmus zu implementieren. (wobei ich nicht weiß, welche Definition von Dijkstra du kennst).

Hier einfach Mal meine Definition:

Sei die Menge V, die Menge der "noch zu bearbeitenden" (also im Sinne von zu "verbessernden-Wege-Knoten").

Vorgehen:
* Du fängst an beim Startknoten
* Du fügst in deine Menge V den Startknoten ein. (ist somit erstes Element in der Menge)
* initialisiere alle Knoten auf MAX_INTEGER.
* setze dist[startknoten] = 0
* REPEAT (solange V !empty): 
** lösche Knoten mit kleinstem Abstand aus V. (zu beginn der Startknoten)
** FOR (w : v.getErreichbareKoten())
*** int neueDist = dist[v] + pGraph.getKnotenKosten (v,w); // hier gehe ich davon aus, dass dein Graph so implementiert ist.
*** if (neueDist < dist[w]){
*** dist[w] = neueDist;
*** V.insert(w);
** END FOR;
* END REPEAT

Bermerkung: dein V ist eben dein "dist[]" wo du bereits mit "gibKleinstenUnbesuchtenKnoten(dist, besucht)" das kleinste-Distanz-Element heraussuchst.

Fazit:
Wenn du noch eine Methode in deiner pGraph.class implementierst, die mit .getNeighbourNodes() die Nachbarknoten w1, w2, ... wn eines Knotens v ermittelt, so lässt sich der Algorithmus tatsächlich in 13 / 14 Zeilen implementieren.

(Bemerkung: ich habe deinen Code genau gelesen, aber nicht ganz verstanden, leider. Ich sehe ab und zu die Idee von Dijsktra, aber ist iwie zu ungenau)


----------



## Kampfzwereg (11. Jun 2012)

Hi,

schön dass du dich meinem Problem annimmst. Also  ich weiß an sich wie Dijkstra Funktioniert, muss aber zugeben, dass ich mir eine Vorlage aus dem Internet genommen habe um mich an dieser zu  orientieren. Das problem dabei war, dass dieses Beispiel mit ints gearbeitet hat und nicht mit GraphNodes, was mich sehr verwirrt hat. Desswegen erscheint mein Quellcode eventuell so kompliziert, da ich immer von int in GraphNode umwandeln muss indem ich mit whileschleifen durchgehen etc.

Ich werde nocheinmal mit deinem QUellcode rumspielen. Und stelle dann das Ergebnis hier ins Thread. Dann könnteste mir ja nochmal ne Rückmeldung geben. Danke aber schonmal für diese sehr hilfreiche Kritik.

LG


----------



## NintendoLink07 (11. Jun 2012)

Hier ein Beispiel eines funktionierenden Dijkstra-Algorithmus, um dir vielleicht ein paar Anregungen zu geben:


```
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

class Vertex implements Comparable<Vertex>
{
	public final String name;
	public Edge[] adjacencies;
	public double minDistance = Double.POSITIVE_INFINITY;
	public Vertex previous;
	public Vertex(String argName) { name = argName; }
	public String toString() { return name; }
	public int compareTo(Vertex other)
	{
		return Double.compare(minDistance, other.minDistance);
	}
}

class Edge
{
	public final Vertex target;
	public final double weight;
	public Edge(Vertex argTarget, double argWeight)
	{ target = argTarget; weight = argWeight; }
}


public class Dijkstra
{

	public static List<Vertex> getShortestPathTo(Vertex target)
	{
	    List<Vertex> path = new ArrayList<Vertex>();
	    for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
		path.add(vertex);

	    Collections.reverse(path);
	    return path;
	}

	public static void computePaths(Vertex source)
	{
		source.minDistance = 0.;
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		vertexQueue.add(source);

		while (!vertexQueue.isEmpty())
		{
			Vertex u = vertexQueue.poll();

			for (Edge e : u.adjacencies)
			{
				Vertex v = e.target;
				double weight = e.weight;
				double distanceThroughU = u.minDistance + weight;

				if (distanceThroughU < v.minDistance)
				{
					vertexQueue.remove(v);
					v.minDistance = distanceThroughU ;
					v.previous = u;
					vertexQueue.add(v);
				}
			}
		}
	}

	public static void main (String[]args)
	{
		Vertex v0 = new Vertex("Harrisburg");
		Vertex v1 = new Vertex("Baltimore");
		Vertex v2 = new Vertex("Washington");
		Vertex v3 = new Vertex("Philadelphia");
		Vertex v4 = new Vertex("Binghamton");
		Vertex v5 = new Vertex("Allentown");
		Vertex v6 = new Vertex("New York");

		v0.adjacencies = new Edge[]{ new Edge(v1,  79.83),
		                             new Edge(v5,  81.15) };
		v1.adjacencies = new Edge[]{ new Edge(v0,  79.75),
		                             new Edge(v2,  39.42),
		                             new Edge(v3, 103.00) };
		v2.adjacencies = new Edge[]{ new Edge(v1,  38.65) };
		v3.adjacencies = new Edge[]{ new Edge(v1, 102.53),
		                             new Edge(v5,  61.44),
		                             new Edge(v6,  96.79) };
		v4.adjacencies = new Edge[]{ new Edge(v5, 133.04) };
		v5.adjacencies = new Edge[]{ new Edge(v0,  81.77),
		                             new Edge(v3,  62.05),
		                             new Edge(v4, 134.47),
		                             new Edge(v6,  91.63) };
		v6.adjacencies = new Edge[]{ new Edge(v3,  97.24),
		                             new Edge(v5,  87.94) };

		Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };

		computePaths(v0);

		for (Vertex v : vertices)
		{
		    System.out.println("Distanz zu " + v + ": " + v.minDistance);
		    List<Vertex> path = getShortestPathTo(v);
		    System.out.println("Pfad: " + path + "\n");
		}
	}

}
```


----------



## Kampfzwereg (11. Jun 2012)

jo danke sehr. werd mir den nochmal angucken.... 

ich hab zwar das Prinzip des Algorythmus verstanden, glaube jedoch, die Umsetztung nicht ganz.
In dem Beispiel das ich mir angeguckt habe arbeitet er jedenfalls mit integers, und nicht mit GraphNodes. Ist das richtig so. 
Man muss aber auch sagen, dass der Verfasser auf Methoden zurückgegriffen hat,  welche keine Standardmethoden sind. Desshalb musste ich Umständliche umwege eingbauen....

(Bin gerade nicht zuhause, schicke den Link zu dme Beispiel nochmal heute nachmittag)


----------



## Kampfzwereg (20. Jun 2012)

ok hab das ganze jetzt nochmal überarbeitet...wie siehts denn jetzt damit aus ....? 


```
public class DijkstraRechner {
    
    private Graph myGraph = new Graph();
    public GraphNode[] knotenArray;
    public int[] dist;
    public GraphNode[] prev;
    public boolean[] besucht;   
    
    
       
    
    public List berechneWegZuEinem(Graph pGraph, GraphNode pStart, GraphNode pZiel)
    {
        int zaehler = 0; 
        List knoten = pGraph.getNodes();
        knoten.toFirst();
        while(knoten.hasAccess())
        {
            zaehler++;
        }
        knotenArray = new GraphNode[zaehler];
        dist = new int[zaehler];
        prev= new GraphNode[zaehler];
        besucht= new boolean[zaehler];
        knoten.toFirst();
        for(int i=0; i<zaehler;i++)
        {
            knotenArray[i]=(GraphNode)knoten.getObject();
            dist[i]=Integer.MAX_VALUE;
            prev[i]=null;
        }
        
        
        List wegZuZiel = new List();               
        GraphNode[] wegZuAllen = berechneWegZuAllen(pGraph, pStart, knotenArray, dist, prev, besucht);
        zaehler = 0; 
        while(zaehler != knotenArray.length && knotenArray[zaehler] != pZiel)
        {
           zaehler++;           
        }
        wegZuZiel.append(knotenArray[zaehler]);
        zaehler=0;
        
    
        
        while(knotenArray[zaehler] != pStart)
        {
            
            GraphNode temp = (GraphNode)prev[zaehler];
            int tempzaehler =0;
            while(temp != (GraphNode)knotenArray[tempzaehler])
            {
                tempzaehler++;
            }       
            wegZuZiel.insert(knotenArray[zaehler]);
            wegZuZiel.toFirst();           
            zaehler = tempzaehler;            
        }
        return wegZuZiel;
    }
    
    private GraphNode[] berechneWegZuAllen(Graph pGraph, GraphNode pStart, GraphNode[] knotenArray, int[] dist, GraphNode[] prev, boolean[] besucht)
    {
        if(pStart == null)
        {                 
            int zaehler = 0;
            while(knotenArray[zaehler] != pStart)
            {
                zaehler++;
            }     
            dist[zaehler] = 0;
            besucht[zaehler] = true;
            for(int i=0; i<dist.length; i++)
            {
                int naechster = gibKleinstenUnbesuchtenKnoten(dist, besucht);
                besucht[naechster] = true;           
                GraphNode tempNode = (GraphNode) knotenArray[naechster];            
                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 = knotenArray[tempZaehler];
                    int d = (int)dist[naechster] + (int)pGraph.getEdgeWeight(tempNode, tempNode2);
                    if(dist[tempZaehler] > d)
                    {
                        dist[tempZaehler] = d;
                        prev[tempZaehler] = knotenArray[naechster];
                    }
                }
            }   
            return prev;
        }
        else
        {
           System.out.println("Funktioniert 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;
    }
    


    
}
```


----------



## SlaterB (20. Jun 2012)

130 Zeilen Code einfach so zu interpretieren ist nicht leicht,
wenn du wenigstens ein vollständiges Programm mit main-Methode mit Beispielgraph draus machen würdest,
so wie von NintendoLink07 vorbildlich gepostet,

idealerweise dessen Graph nachbauen, dann kann man mglw. super vergleichen


----------



## Kampfzwereg (20. Jun 2012)

was macht denn das für einen unterschied , nurmal so ? ^^


----------



## SlaterB (20. Jun 2012)

man könnte Ausgaben reinsetzen, sehen was sich zwischen den Methoden (unbekannter Funktion) ändert usw.


----------

