Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen

M

Mark 1912

Mitglied
Hallo,

ich schreibe gerade ein Programm, in dem ich in einem Graphen zu aufkommenden Notrufen an verschiedenen Knoten nächstgelegene Fahrzeuge zuweise. Diese will ich mit dem Dijkstra Algorithmus ausfindig machen. Den Dijkstra habe ich von einer anderen Seite übernommen und ihn auch vorher getestet, er funktioniert für einen Knoten. Die vorletzte Zeile mit "settledNodes.clear()" habe ich hinzugefügt, damit das Set mit allen Knoten nach dem Durchlaufen wiedergelöscht wird.

Java: 
import java.util.HashSet;
import java.util.Set;
import java.util.LinkedList;
import java.util.Map.Entry;

public class Dijkstra {
      public static Node getLowestDistanceNode(Set<Node> unsettledNodes) {
            Node lowestDistanceNode = null;
            int lowestDistance = Integer.MAX_VALUE;
            for (Node node : unsettledNodes) {
                int nodeDistance = node.getDistance();
                if (nodeDistance < lowestDistance) {
                    lowestDistance = nodeDistance;
                    lowestDistanceNode = node;
                }
            }
            return lowestDistanceNode;
            
            
            
    }
      GraphDijkstra graph2;
      private static void CalculateMinimumDistance(Node evaluationNode, Integer edgeWeigh, Node sourceNode) {
            Integer sourceDistance = sourceNode.getDistance();
            if (sourceDistance + edgeWeigh < evaluationNode.getDistance()) {
                evaluationNode.setDistance(sourceDistance + edgeWeigh);
                LinkedList<Node> shortestPath = new LinkedList<>(sourceNode.getShortestPath());
                shortestPath.add(sourceNode);
                evaluationNode.setShortestPath(shortestPath);
            }
        }
      
    public static GraphDijkstra calculateShortestPathFromSource(GraphDijkstra graph, Node source) {
        source.setDistance(0);
    
        Set<Node> settledNodes = new HashSet<>();
        Set<Node> unsettledNodes = new HashSet<>();
    
        unsettledNodes.add(source);
    
        while (unsettledNodes.size() != 0) {
            Node currentNode = getLowestDistanceNode(unsettledNodes);
            unsettledNodes.remove(currentNode);
            for (Entry < Node, Integer> adjacencyPair:
              currentNode.getAdjacentNodes().entrySet()) {
                Node adjacentNode = adjacencyPair.getKey();
                Integer edgeWeight = adjacencyPair.getValue();
                if (!settledNodes.contains(adjacentNode)) {
                    CalculateMinimumDistance(adjacentNode, edgeWeight, currentNode);
                    unsettledNodes.add(adjacentNode);
                }
            }
            settledNodes.add(currentNode);
        }
        settledNodes.clear();
        return graph ;
    }
    
    
    
    }

Meine Frage ist nun, wie ich die Methode "calculateShortestPathFromSource" ändern muss, dass die berechneten Pfadlängen wieder zurückgesetzt werden. Denn wenn ich meinen Graph erstelle und für verschiedene Knoten die Methode aufrufe, werden die Distanzen vom ersten Aufruf übernommen. Ich füge auch meine Main Methode mit dem Graph und den Ausgaben ein(die Ausgaben sind:

Knoten 2Distanz 8
Distanz zu Knoten A0
Distanz zu Knoten B20
Knoten 3Distanz 7
Distanz zu Knoten A0
Distanz zu Knoten B0)

Wie man sehen kann bleibt die Distanz zu Knoten A bei Null, obwohl ich eigentlich nun Knoten B betrachte, habe ich irgendwo einen Denkfehler oder geht das mit diesem Ansatz grundsätzlich nicht?

Vielen Dank schon mal im Voraus!



Java: 
public static void main(String[]args){
        Node nodeA = new Node(false,0,null,0);
        Node nodeB = new Node(true,1,null,0);
        Node nodeC = new Node(false,2,null,0);
        Node nodeD = new Node(false,3,null,0);
        Node nodeE = new Node(false,4,null,0);
        Node nodeF = new Node(true,5,null,0);
        Node nodeG = new Node(false,6,null,0);
        Node nodeH = new Node(false,7,null,0);
        Node nodeI = new Node(false,8,null,0);
        Node nodeJ = new Node(true,9,null,0);
        Node nodeK = new Node(false,10,null,0);
            
        nodeA.addDestination(nodeB, 20);
        nodeA.addDestination(nodeC, 8);
        nodeA.addDestination(nodeE, 9);
        
        nodeB.addDestination(nodeA, 20);
        nodeB.addDestination(nodeD, 7);
        nodeB.addDestination(nodeI, 17);
        
        nodeC.addDestination(nodeA, 8);
        nodeC.addDestination(nodeE, 8);
        nodeC.addDestination(nodeF, 5);
        nodeC.addDestination(nodeJ, 10);
        
        nodeD.addDestination(nodeB, 7);
        nodeD.addDestination(nodeF, 6);
        nodeD.addDestination(nodeH, 5);
        
        nodeE.addDestination(nodeC, 8);
        nodeE.addDestination(nodeA, 9);
        nodeE.addDestination(nodeJ, 10);
        
        nodeF.addDestination(nodeC, 5);
        nodeF.addDestination(nodeD, 6);
        nodeF.addDestination(nodeG, 4);
        nodeF.addDestination(nodeH, 5);
        
        nodeG.addDestination(nodeF, 4);
        nodeG.addDestination(nodeH, 4);
        nodeG.addDestination(nodeJ, 8);
        nodeG.addDestination(nodeK, 7);
        
        nodeH.addDestination(nodeD, 5);
        nodeH.addDestination(nodeG, 4);
        nodeH.addDestination(nodeF, 5);
        nodeH.addDestination(nodeI, 6);
        
        nodeI.addDestination(nodeH, 6);
        nodeI.addDestination(nodeB, 17);
        nodeI.addDestination(nodeK, 8);
        
        nodeJ.addDestination(nodeG, 8);
        nodeJ.addDestination(nodeE, 10);
        nodeJ.addDestination(nodeC, 10);
        nodeJ.addDestination(nodeK, 9);
        
        nodeK.addDestination(nodeJ, 9);
        nodeK.addDestination(nodeI, 8);
        nodeK.addDestination(nodeG, 7);
        
        GraphDijkstra graph = new GraphDijkstra();
        
        graph.addNode(nodeA);
        graph.addNode(nodeB);
        graph.addNode(nodeC);
        graph.addNode(nodeD);
        graph.addNode(nodeE);
        graph.addNode(nodeF);
        graph.addNode(nodeG);
        graph.addNode(nodeH);
        graph.addNode(nodeI);
        graph.addNode(nodeJ);
        graph.addNode(nodeK);
        
        Set<Node> fahrzeugNodes = new HashSet<>();
         fahrzeugNodes.add(nodeC);
         fahrzeugNodes.add(nodeD);
         fahrzeugNodes.add(nodeF);
         fahrzeugNodes.add(nodeG);
         fahrzeugNodes.add(nodeH);
              
       
   
        calculateShortestPathFromSource(graph, nodeA);
        System.out.print("Knoten "+getLowestDistanceNode(fahrzeugNodes).knotennummer);
        System.out.println("Distanz "+getLowestDistanceNode(fahrzeugNodes).distance);
        System.out.println("Distanz zu Knoten A"+nodeA.distance);
        System.out.println("Distanz zu Knoten B"+nodeB.distance);
        calculateShortestPathFromSource(graph, nodeB);
        System.out.print("Knoten "+getLowestDistanceNode(fahrzeugNodes).knotennummer);
        System.out.println("Distanz "+getLowestDistanceNode(fahrzeugNodes).distance);
        System.out.println("Distanz zu Knoten A"+nodeA.distance);
        System.out.println("Distanz zu Knoten B"+nodeB.distance);
   
    }
 
Nimm a*.

Richtigerweise berechnet Dijkstra aber die Entfernung jedes Knotens zum target source Knoten.

Demzufolge wäre deins falsch...
 
Berechnet a* nicht nur den kürzesten Pfad zwischen zwei Knoten?
Ich möchte aber auch den nächstgelegenen Knoten zu meinem Source Knoten haben, wovon ich dachte, dass dort Dijkstra anzuwenden wäre. Mein Problem ist, dass die Werte für die Pfadlängen schon geupdated wurden und ich nicht einen zweiten Aufruf von einem anderen Knoten starten kann.

Mein Ausgabe waren vielleicht ein bisschen missverständlich diesbezüglich, denn ich möchte meistens immer die Funktion getLowestDistanceNode auf den Dijkstra Graph anwenden und den nächstgelegenen Knoten zu einem beliebigem Startknoten finden.
Laut Wikipedia ("Für das Beispiel der Wegsuche ist der Dijkstra-Algorithmus besser geeignet, falls das Ziel nicht bereits vor der Wegsuche bekannt ist (z. B. nächste Tankstelle), und daher die Verwendung einer Heuristik nicht möglich ist. ") soll man in meinem Fall auch eher den Dijkstra verwenden.

Kann ich also vielleicht eine neue Methode erstellen, die die Ausgabe von der Methode calculateshortestPath zurücksetzt?
Also etwas in diese Richtung? Nur weiß ich gerade nicht genau, wie genau ich den Output vom Dijkstra oder der Methode calculateshortestPath rückgängig machen kann.
Java: 
public static GraphDijkstra setzeGraphzurück(GraphDijkstra graph){
        //Setze Graphen auf ursprügnliche Kantenbewertungen zurück
        
        return graph;
    }
 
Zuletzt bearbeitet:
Oder muss ich in meiner Klasse Node, die gespeicherten Werte für alle Knoten zurücksetzen? Kann es auch sein, dass ich "Integer distance" zurück bzw auf null setzen muss, da die Distanzen für meine Knoten gespeichert wurden?

Java: 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Node {
   
   
    boolean besitztKrankenhaus;
    List <Fahrzeug> fahrzeuge=new LinkedList<>();
    int knotennummer;
    int Bevölkerung;//in Tausend
    ArrayList<Fahrzeug> fahrzeuge2 = new ArrayList<>();
    Set<Fahrzeug> Fahrzeuge = new HashSet<>();
    int y_bedarfalt;//BEdarf aus t-1
    public Node(boolean besitzt,int kn,ArrayList<Fahrzeug> fahrzeuge_2,int y){
        besitztKrankenhaus=besitzt;
        knotennummer=kn;
        fahrzeuge2=fahrzeuge_2;
        y_bedarfalt=y;
       
    }
   
    List<Node> shortestPath = new LinkedList<>();
   
    Integer distance = Integer.MAX_VALUE;
   
    Map<Node, Integer> adjacentNodes = new HashMap<>();
   

    public void addDestination(Node destination, int distance) {
        adjacentNodes.put(destination, distance);
    }



    public Map<Node, Integer> getAdjacentNodes() {
        return adjacentNodes;
    }

    public void setAdjacentNodes(Map<Node, Integer> adjacentNodes) {
        this.adjacentNodes = adjacentNodes;
    }

    public Integer getDistance() {
        return distance;
    }

    public void setDistance(Integer distance) {
        this.distance = distance;
    }

    public List<Node> getShortestPath() {
        return shortestPath;
    }

    public void setShortestPath(LinkedList<Node> shortestPath) {
        this.shortestPath = shortestPath;
    }

    public void reset() {
        shortestPath.clear();
       
        // TODO Auto-generated method stub
       
    }

   


}
 
Zuletzt bearbeitet:
Ich habe eben eine mögliche Lösung gefunden, dadurch dass ich mit:
Java: 
for(Node node : all) {       
            node.distance = Integer.MAX_VALUE;
        }
die Distanz zu jedem Knoten wieder zurücksetze (aufs Maximum).
 
Mh, ohne Prioritätswarteschlange (Priorityqueue...), ist Dein Dijkstra auch nicht wirklich "effizient".
Wenn Du mir nochmal kurz schreibst, was wie gegeben ist, also wie Deine Struktur ausschaut, dann kann ich das vielleicht gerad einmal machen - so dass Du dann von einem Startknoten die kürzesten Wege zu allen anderen Knoten hättest. 🙂
 
Ok, vielen Dank! 🙂
Also wegen Effizienz habe ich mir noch keine Sorgen gemacht, weil mein Graph nur aus 11 Knoten besteht und die Ausgabe innerhalb von ca 1 Sekunde erfolgt.
Also meine Klasse Dijkstra mit dem Dijkstra habe ich ja schon geschickt, nur dass es dort keine Main Methode gibt. Die Berechnungen finden alle in einer Klasse Disposition statt, wo auch mein Graph erstellt wird. Diesem liegen Knoten zugrunde, die auf der Klasse "Node" (siehe oben) basieren. Den Graphen erstelle ich mit Hilfe der Klasse "Graph Dijkstra":
Java: 
import java.util.*;
public class GraphDijkstra {
    public Set<Node> nodes = new HashSet<>();
  
    public void addNode(Node nodeA) {
        nodes.add(nodeA);
    }

    // getters and setters
    public Set<Node> getNodes() {
        return nodes;
    }

    public void setNodes(Set<Node> nodes) {
        this.nodes = nodes;
}


}

In meinem Beispiel erstelle ich eine Simulation eines fiktiven Graphen mit 11 Knoten, den ich ein bisschen an ein bestehendes Netzwerk schon angelehnt habe. Dazu habe ich an 5 Knoten insgesamt 7 Fahrzeuge, also an zwei Knoten jeweils zwei, dazu habe ich unten mal die Klasse Fahrzeuge angehängt. Die Fahrzeuge sind von Beginn an verfügbar, aber sobald sie einen Einsatz fahren sind sie für die Dauer des Einsatzes nicht verfügbar.

Java: 
public class Fahrzeug {
    boolean verfügbar;
    //public static boolean frei=true;
    //public static boolean belegt=false;
    int knoten;
    int fahrzeithin;
    int fahrzeitzurück;
    int fahrzeitkrankenhaus;
    int fahrzeitgesamt;
    int einsatzstunde;
    int einsatzminute;
    int fahrzeugnr;
    public Fahrzeug(boolean v,int k, int fahin, int fahzu, int fahk, int fahges,int eist, int eimin,int fahrnr){
      
        verfügbar=v;
        knoten=k;
        fahrzeithin=fahin;
        fahrzeitzurück=fahzu;
        fahrzeitkrankenhaus=fahk;
        fahrzeitgesamt=fahges;
        einsatzstunde=eist;
        einsatzminute=eimin;
        fahrzeugnr=fahrnr;
      
    }

Ich habe dann in meiner Main Methode zwei verschachtelte for Schleifen, die meinen Tagesablauf darstellen und innerhalb dieser lasse ich Bedarfe aufkommen, die einer Poissonverteilung folgen. Falls ein Bedarf an einem Knoten aufkommt, soll das nächstgelegene, verfügbare Fahrzeug aus dem Set der Fahrzeugknoten gefunden werden. Dazu dann auch das nächstgelegene Krankenhaus aus einem Set bestehend aus drei der 11 Knoten. Dann wird das Fahrzeug auf nicht verfügbar gesetzt und ist erst wieder verfügbar, wenn die Gesamtfahrzeit vergangen ist.

Ich füge, falls du die Main Methode in der Klasse Disposition brauchst, auch diese an, aber sie ist sehr statisch und sehr lang, weil ich noch 10 weitere Knoten genauso ausführe, aber sie funktioniert.


Code: 
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Disposition {
    static Node nächsterKnoten;
    static Fahrzeug ausgewähltesFahrzeug;
    static Node krankenhaus;
    static Node einsatzknoten;
   
    public static void main(String []args){
        Fahrzeug fahr1 = new Fahrzeug(true,2,0,0,0,0,0,0,1);
        Fahrzeug fahr2 = new Fahrzeug(true,3,0,0,0,0,0,0,2);
        Fahrzeug fahr3 = new Fahrzeug(true,3,0,0,0,0,0,0,3);
        Fahrzeug fahr4 = new Fahrzeug(true,5,0,0,0,0,0,0,4);
        Fahrzeug fahr5 = new Fahrzeug(true,6,0,0,0,0,0,0,5);
        Fahrzeug fahr6 = new Fahrzeug(true,7,0,0,0,0,0,0,6);
        Fahrzeug fahr7 = new Fahrzeug(true,7,0,0,0,0,0,0,7);
       
               
        ArrayList<Fahrzeug> fahrzeuge2knoten2 = new ArrayList<>();
        fahrzeuge2knoten2.add(fahr1);
        fahrzeuge2knoten2.add(null);
       
        ArrayList<Fahrzeug> fahrzeuge2knoten3 = new ArrayList<>();
        fahrzeuge2knoten3.add(fahr2);
        fahrzeuge2knoten3.add(fahr3);
       
        ArrayList<Fahrzeug> fahrzeuge2knoten4 = new ArrayList<>();
        fahrzeuge2knoten4.add(fahr4);
        fahrzeuge2knoten4.add(null);
       
        ArrayList<Fahrzeug> fahrzeuge2knoten5 = new ArrayList<>();
        fahrzeuge2knoten5.add(fahr5);
        fahrzeuge2knoten5.add(null);
       
        ArrayList<Fahrzeug> fahrzeuge2knoten6 = new ArrayList<>();
        fahrzeuge2knoten6.add(fahr6);
        fahrzeuge2knoten6.add(fahr7);
       
        Node nodeA = new Node(false,0,null,0);
        Node nodeB = new Node(true,1,null,0);
        Node nodeC = new Node(false,2,fahrzeuge2knoten2,0);
        Node nodeD = new Node(false,3,fahrzeuge2knoten3,0);
        Node nodeE = new Node(false,4,null,0);
        Node nodeF = new Node(true,5,fahrzeuge2knoten4,0);
        Node nodeG = new Node(false,6,fahrzeuge2knoten5,0);
        Node nodeH = new Node(false,7,fahrzeuge2knoten6,0);
        Node nodeI = new Node(false,8,null,0);
        Node nodeJ = new Node(true,9,null,0);
        Node nodeK = new Node(false,10,null,0);
       
        Node all []={nodeA,nodeB,nodeC,nodeD,nodeE,nodeF,nodeG,nodeH,nodeI,nodeJ,nodeK};
           
        nodeA.addDestination(nodeB, 20);
        nodeA.addDestination(nodeC, 8);
        nodeA.addDestination(nodeE, 9);
       
        nodeB.addDestination(nodeA, 20);
        nodeB.addDestination(nodeD, 7);
        nodeB.addDestination(nodeI, 17);
       
        nodeC.addDestination(nodeA, 8);
        nodeC.addDestination(nodeE, 8);
        nodeC.addDestination(nodeF, 5);
        nodeC.addDestination(nodeJ, 10);
       
        nodeD.addDestination(nodeB, 7);
        nodeD.addDestination(nodeF, 6);
        nodeD.addDestination(nodeH, 5);
       
        nodeE.addDestination(nodeC, 8);
        nodeE.addDestination(nodeA, 9);
        nodeE.addDestination(nodeJ, 10);
       
        nodeF.addDestination(nodeC, 5);
        nodeF.addDestination(nodeD, 6);
        nodeF.addDestination(nodeG, 4);
        nodeF.addDestination(nodeH, 5);
       
        nodeG.addDestination(nodeF, 4);
        nodeG.addDestination(nodeH, 4);
        nodeG.addDestination(nodeJ, 8);
        nodeG.addDestination(nodeK, 7);
       
        nodeH.addDestination(nodeD, 5);
        nodeH.addDestination(nodeG, 4);
        nodeH.addDestination(nodeF, 5);
        nodeH.addDestination(nodeI, 6);
       
        nodeI.addDestination(nodeH, 6);
        nodeI.addDestination(nodeB, 17);
        nodeI.addDestination(nodeK, 8);
       
        nodeJ.addDestination(nodeG, 8);
        nodeJ.addDestination(nodeE, 10);
        nodeJ.addDestination(nodeC, 10);
        nodeJ.addDestination(nodeK, 9);
       
        nodeK.addDestination(nodeJ, 9);
        nodeK.addDestination(nodeI, 8);
        nodeK.addDestination(nodeG, 7);
       
        GraphDijkstra graph = new GraphDijkstra();
       
        graph.addNode(nodeA);
        graph.addNode(nodeB);
        graph.addNode(nodeC);
        graph.addNode(nodeD);
        graph.addNode(nodeE);
        graph.addNode(nodeF);
        graph.addNode(nodeG);
        graph.addNode(nodeH);
        graph.addNode(nodeI);
        graph.addNode(nodeJ);
        graph.addNode(nodeK);
       
        Set<Node> nodes = new HashSet<>();
        nodes.add(nodeA);
        nodes.add(nodeB);
        nodes.add(nodeC);
        nodes.add(nodeD);
        nodes.add(nodeE);
        nodes.add(nodeF);
        nodes.add(nodeG);
        nodes.add(nodeH);
        nodes.add(nodeI);
        nodes.add(nodeJ);
        nodes.add(nodeK);
       
       
         Set<Node> fahrzeugNodes = new HashSet<>();
         fahrzeugNodes.add(nodeC);
         fahrzeugNodes.add(nodeD);
         fahrzeugNodes.add(nodeF);
         fahrzeugNodes.add(nodeG);
         fahrzeugNodes.add(nodeH);
       
                 
         Set<Node> krankenhausNodes = new HashSet<>();
         krankenhausNodes.add(nodeC);
         krankenhausNodes.add(nodeG);
         krankenhausNodes.add(nodeK);
       
       
        //Krankentransporte zuweisen
        Krankentransport kt1 = new Krankentransport(8,34,1,2,15,8,49,nodeB);
        Krankentransport kt2=  new Krankentransport(9,19,8,6,13,9,32,nodeI);
   
for (int stunden=8;stunden<18;++stunden){
     for(int minuten=0;minuten<60;++minuten){
         System.out.println("Uhrzeit = " + stunden +" :"+ minuten);
         System.out.println("Restbedarf"+nodeA.y_bedarfalt+","+nodeB.y_bedarfalt+","+nodeC.y_bedarfalt+","+nodeD.y_bedarfalt+","+nodeE.y_bedarfalt+","+nodeF.y_bedarfalt+","+nodeG.y_bedarfalt+","+nodeH.y_bedarfalt+","+nodeI.y_bedarfalt+","+nodeJ.y_bedarfalt+","+nodeK.y_bedarfalt);
        // Random rnd1= new Random();
         //double x1=rnd1.nextDouble();
         //Bedarfe knoten1 = new Bedarfe(0.565,x1);
         //for(int )
       
         //Verfügbarkeit der Fahrzeuge prüfen
       
         if(stunden>=fahr1.einsatzstunde && minuten>=fahr1.einsatzminute){
             fahr1.verfügbar=true;
         }
       
         if(stunden>=fahr2.einsatzstunde && minuten>=fahr2.einsatzminute){
             fahr2.verfügbar=true;
         }
       
         if(stunden>=fahr3.einsatzstunde && minuten>=fahr3.einsatzminute){
             fahr3.verfügbar=true;
         }
       
         if(stunden>=fahr4.einsatzstunde && minuten>=fahr4.einsatzminute){
             fahr4.verfügbar=true;
         }
       
         if(stunden>=fahr5.einsatzstunde && minuten>=fahr5.einsatzminute){
             fahr5.verfügbar=true;
         }
       
         if(stunden>=fahr6.einsatzstunde && minuten>=fahr6.einsatzminute){
             fahr6.verfügbar=true;
         }
       
         if(stunden>=fahr7.einsatzstunde && minuten>=fahr7.einsatzminute){
             fahr7.verfügbar=true;
         }
       
         //Knoten 1 Bedarf
   
        Random rnd= new Random ();
        double x1=rnd.nextDouble();
        double lambda1=0.565;
        double y1=(lambda1/60)*Math.exp(lambda1/60);
        if(y1>=x1||nodeA.y_bedarfalt>=1){
             if(nodeA.y_bedarfalt>=1){
                 einsatzknoten=nodeA;
                 for(Node node : all) {      
                        node.distance = Integer.MAX_VALUE;
                    }
                 graph = Dijkstra.calculateShortestPathFromSource(graph, einsatzknoten);
                 Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                 fahrzeugNodes.add(nodeC);
                 fahrzeugNodes.add(nodeD);
                 fahrzeugNodes.add(nodeF);
                 fahrzeugNodes.add(nodeG);
                 fahrzeugNodes.add(nodeH);
                for(int i=einsatzknoten.y_bedarfalt;i>0;i--){
                   
               
                 if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                        nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                        Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                        ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);  
                    }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                        if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                        nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                        Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                        ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                        }}//remove nächsten Knoten
                   
                    else {fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                   
                            if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                            nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                            Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                            ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                            }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                                if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                    nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                    Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                                    ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                                    //remove zweitnächsten Knoten
                                   
                                }}else{fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                                    if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                        nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                        Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                                        ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                                    }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                                        if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                            nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                            Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                                            ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                            //remove drittnächsten Knoten
                                           
                            }}else{fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                            if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                                ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                            }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                                if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                    nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                    Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                                    ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                                   
                                }else{fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                                    if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                    nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                    Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                                    ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                                    }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                                        if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                        nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                        Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                                        ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                                        }}else{
                                           
                                           
                                        }
                                }}
                            }      
                    }}
                 ausgewähltesFahrzeug.verfügbar=false;
                     ausgewähltesFahrzeug.fahrzeithin=nächsterKnoten.distance;
                    krankenhaus=Dijkstra.getLowestDistanceNode(krankenhausNodes);
                    ausgewähltesFahrzeug.fahrzeitkrankenhaus=krankenhaus.distance;
                     for(Node node : all) {      
                            node.distance = Integer.MAX_VALUE;
                        }
                    Dijkstra.calculateShortestPathFromSource(graph, krankenhaus);
                    ausgewähltesFahrzeug.fahrzeitzurück=nächsterKnoten.distance;
                    ausgewähltesFahrzeug.fahrzeitgesamt=30+ausgewähltesFahrzeug.fahrzeithin+ausgewähltesFahrzeug.fahrzeitkrankenhaus+ausgewähltesFahrzeug.fahrzeitzurück;
                    ausgewähltesFahrzeug.einsatzstunde=stunden+(ausgewähltesFahrzeug.fahrzeitgesamt/60);
                    ausgewähltesFahrzeug.einsatzminute=minuten+(ausgewähltesFahrzeug.fahrzeitgesamt%60);
                    if(ausgewähltesFahrzeug.einsatzminute>59){
                        ausgewähltesFahrzeug.einsatzminute=ausgewähltesFahrzeug.einsatzminute%60;
                        ausgewähltesFahrzeug.einsatzstunde++;
                    }else{
                       
                    }
                    System.out.println("Fahrzeug wieder verfügbarum "+ausgewähltesFahrzeug.einsatzstunde+":"+ausgewähltesFahrzeug.einsatzminute);
                    System.out.println("Wähle Fahrzeug "+ausgewähltesFahrzeug.fahrzeugnr +" an Knoten "+nächsterKnoten.knotennummer+" mit Distanz "+ausgewähltesFahrzeug.fahrzeithin+" und Krankenhaus "+krankenhaus.knotennummer);
                    System.out.println("Fahrzeit gesamt " +ausgewähltesFahrzeug.fahrzeitgesamt+", Fahrzeit zum Krankenhaus "+ausgewähltesFahrzeug.fahrzeitkrankenhaus+", Fahrzeit zurück zum Ruhepunkt "+ausgewähltesFahrzeug.fahrzeitzurück);
                    einsatzknoten.y_bedarfalt--;
             }}
             else{
               
             }
             if(y1>=x1){
           
             fahrzeugNodes.add(nodeC);
             fahrzeugNodes.add(nodeD);
             fahrzeugNodes.add(nodeF);
             fahrzeugNodes.add(nodeG);
             fahrzeugNodes.add(nodeH);
             for(Node node : all) {      
                    node.distance = Integer.MAX_VALUE;
                }
             System.out.println("Einsatz an Knoten 1");
             einsatzknoten=nodeA;
             //Berechne nächstegelegenes freies Fahrzeug
            Dijkstra.calculateShortestPathFromSource(graph, einsatzknoten);
            if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);  
            }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                }}//remove nächsten Knoten
           
            else {fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
           
                    if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                    nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                    Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                    ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                    }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                        if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                            nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                            Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                            ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                            //remove zweitnächsten Knoten
                           
                        }}else{fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                            if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                                ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                            }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                                if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                    nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                    Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                                    ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                    //remove drittnächsten Knoten
                                   
                    }}else{fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                    if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                        nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                        Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                        ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                    }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                        if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                            nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                            Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                            ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                           
                        }else{fahrzeugNodes.remove(Dijkstra.getLowestDistanceNode(fahrzeugNodes));
                            if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                            nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                            Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0).verfügbar=false;
                            ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(0);
                            }else if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1)!=null){
                                if(Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar&&Dijkstra.getLowestDistanceNode(fahrzeugNodes).distance<=15){
                                nächsterKnoten=Dijkstra.getLowestDistanceNode(fahrzeugNodes);
                                Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1).verfügbar=false;
                                ausgewähltesFahrzeug=Dijkstra.getLowestDistanceNode(fahrzeugNodes).fahrzeuge2.get(1);
                                }}else{
                                    einsatzknoten.y_bedarfalt++;
                                }
                        }}
                    }      
            }}
                           
            ausgewähltesFahrzeug.verfügbar=false;
            ausgewähltesFahrzeug.fahrzeithin=nächsterKnoten.distance;
            krankenhaus=Dijkstra.getLowestDistanceNode(krankenhausNodes);
            ausgewähltesFahrzeug.fahrzeitkrankenhaus=krankenhaus.distance;
             for(Node node : all) {      
                    node.distance = Integer.MAX_VALUE;
                }
            Dijkstra.calculateShortestPathFromSource(graph, krankenhaus);
            ausgewähltesFahrzeug.fahrzeitzurück=nächsterKnoten.distance;
            ausgewähltesFahrzeug.fahrzeitgesamt=30+ausgewähltesFahrzeug.fahrzeithin+ausgewähltesFahrzeug.fahrzeitkrankenhaus+ausgewähltesFahrzeug.fahrzeitzurück;
            ausgewähltesFahrzeug.einsatzstunde=stunden+(ausgewähltesFahrzeug.fahrzeitgesamt/60);
            ausgewähltesFahrzeug.einsatzminute=minuten+(ausgewähltesFahrzeug.fahrzeitgesamt%60);
            if(ausgewähltesFahrzeug.einsatzminute>59){
                ausgewähltesFahrzeug.einsatzminute=ausgewähltesFahrzeug.einsatzminute%60;
                ausgewähltesFahrzeug.einsatzstunde++;
            }else{
               
            }
            System.out.println("Fahrzeug wieder verfügbarum "+ausgewähltesFahrzeug.einsatzstunde+":"+ausgewähltesFahrzeug.einsatzminute);
            System.out.println("Wähle Fahrzeug "+ausgewähltesFahrzeug.fahrzeugnr +" an Knoten "+nächsterKnoten.knotennummer+" mit Distanz "+ausgewähltesFahrzeug.fahrzeithin+" und Krankenhaus "+krankenhaus.knotennummer);
            System.out.println("Fahrzeit gesamt " +ausgewähltesFahrzeug.fahrzeitgesamt+", Fahrzeit zum Krankenhaus "+ausgewähltesFahrzeug.fahrzeitkrankenhaus+", Fahrzeit zurück zum Ruhepunkt "+ausgewähltesFahrzeug.fahrzeitzurück);
                   
                    //if(stunden<stundenkt1)              
           
            }
     }
 
Hallo nochmal, es ist etwas länger und komplizierter geworden als angenommen. Aufgrund einer verwendeten Adjazenzmatrix. Aber das kannst Du so nehmen mit Deiner Fahrzeug -Klasse. Diese muss aber equals() überschreiben...
Java: 
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Dijkstra<T> {
	ArrayList<T> nodes = new ArrayList<>();
	int[][] distances = new int[0][0];

	void addNode(T t) {
		nodes.add(t);
		int n = nodes.size();
		int[][] ndistances = new int[n][n];
		for (int i = 0; i < distances.length; i++) {
			for (int j = 0; j < distances.length; j++) {
				ndistances[i][j] = distances[i][j];
			}
		}
		distances = ndistances;
	}

	int getInx(T t) {
		for (int i = 0; i < distances.length; i++) {
			if (t.equals(nodes.get(i))) {
				return i;
			}
		}
		return -1;
	}

	void addDistance(T t1, T t2, int distance) {
		distances[getInx(t1)][getInx(t2)] = distance;
	}

	PriorityQueue<El<T>> dijkstra(T t1, T t2) {
		PriorityQueue<El<T>> q1 = new PriorityQueue<>();
		PriorityQueue<El<T>> q2 = new PriorityQueue<>();
		for (T t : nodes) {
			if (t.equals(t1)) {
				q1.add(new El<T>(t, 0));
			} else {
				q1.add(new El<T>(t, Integer.MAX_VALUE));
			}
		}
		while (!q1.isEmpty()) {
			El<T> el = q1.remove();
			q2.add(el);
			el.visited = true;
			int i = getInx(el.t);
			for (int j = 0; j < distances.length; j++) {
				if (j != i && distances[i][j] > 0) {
					for (El<T> el2 : q1) {
						if (el2.t.equals(nodes.get(j))) {
							if (!el2.visited) {
								int x = el.d + distances[i][j];
								if (x < el2.d) {
									el2.d = x;
									el2.pre = el;
								}
							}
						}
					}
				}
			}
		}
		return q2;
	}

	public static void main(String[] args) {
		Dijkstra<String> d = new Dijkstra<>();
		d.addNode("a");
		d.addNode("b");
		d.addNode("c");
		d.addNode("d");
		d.addNode("e");
		d.addDistance("a", "b", 1);
		d.addDistance("b", "c", 2);
		d.addDistance("a", "c", 4);
		d.addDistance("a", "d", 1);
		d.addDistance("b", "d", 1);
		d.addDistance("c", "d", 1);
		d.addDistance("a", "e", 3);
		d.addDistance("e", "c", 1);
		PriorityQueue<El<String>> q = d.dijkstra("a", "c");
		for (El<String> el : q) {
			System.out.print(el.t);
			El<String> e = el.pre;
			while (e != null) {
				System.out.print(" <- " + e.t);
				e = e.pre;
			}
			System.out.println(" (" + el.d + ")");
		}
	}
}

class El<T> implements Comparable<El<T>> {
	T t = null;
	int d = 0;
	El<T> pre = null;
	boolean visited = false;

	El(T t, int d) {
		super();
		this.t = t;
		this.d = d;
	}

	@Override
	public int compareTo(El<T> o) {
		return d - o.d;
	}
}


Für das Beispiel erzeugt es eine Ausgabe:
Code: 
a (0)
b <- a (1)
d <- a (1)
e <- a (3)
c <- b <- a (3)


Ändert man die Distanz von a nach e zB auf 2, dann wird dieser Pfad gewählt...
 
Nochmal Hallo, zweite Variante. Diesmal nicht mit der dafür nicht vorgesehenen Adjazenzmatrix und etwas "entzerrt", aber an einer Stelle noch etwas "unschön":
Java: 
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Dijkstra<T> {
	ArrayList<T> nodes = new ArrayList<>();
	int[][] distances = new int[0][0];

	void addNode(T t) {
		nodes.add(t);
		int n = nodes.size();
		int[][] ndistances = new int[n][n];
		for (int i = 0; i < distances.length; i++) {
			for (int j = 0; j < distances.length; j++) {
				ndistances[i][j] = distances[i][j];
			}
		}
		distances = ndistances;
	}

	int getInx(T t) {
		for (int i = 0; i < distances.length; i++) {
			if (t.equals(nodes.get(i))) {
				return i;
			}
		}
		return -1;
	}

	void addDistance(T t1, T t2, int distance) {
		distances[getInx(t1)][getInx(t2)] = distance;
	}

	PriorityQueue<Element<T>> dijkstra(T t1, T t2) {
		ArrayList<Element<T>> list = new ArrayList<>();
		for (T t : nodes) {
			if (t.equals(t1)) {
				list.add(new Element<T>(t, 0));
			} else {
				list.add(new Element<T>(t, Integer.MAX_VALUE));
			}
		}
		for (int i = 0; i < distances.length; i++) {
			for (int j = 0; j < distances[i].length; j++) {
				if (i != j && distances[i][j] > 0) {
					list.get(i).addNext(list.get(j));
				}
			}
		}

		PriorityQueue<Element<T>> q1 = new PriorityQueue<>();
		PriorityQueue<Element<T>> q2 = new PriorityQueue<>();
		q1.addAll(list);

		while (!q1.isEmpty()) {
			Element<T> element1 = q1.remove();
			q2.add(element1);
			element1.visited = true;
			for (Element<T> element2 : element1.nexts) {
				if (!element2.visited) {
					int x = element1.distance + distances[getInx(element1.t)][getInx(element2.t)];
					if (x < element2.distance) {
						element2.distance = x;
						element2.pre = element1;
					}
				}
			}
		}

		return q2;
	}

	public static void main(String[] args) {
		Dijkstra<String> d = new Dijkstra<>();
		d.addNode("a");
		d.addNode("b");
		d.addNode("c");
		d.addNode("d");
		d.addNode("e");
		d.addDistance("a", "b", 1);
		d.addDistance("b", "c", 2);
		d.addDistance("a", "c", 4);
		d.addDistance("a", "d", 10);
		d.addDistance("b", "d", 10);
		d.addDistance("c", "d", 1);
		d.addDistance("a", "e", 3);
		d.addDistance("e", "c", 1);
		PriorityQueue<Element<String>> q = d.dijkstra("a", "c");
		for (Element<String> el : q) {
			System.out.print(el.t);
			Element<String> e = el.pre;
			while (e != null) {
				System.out.print(" <- " + e.t);
				e = e.pre;
			}
			System.out.println(" (" + el.distance + ")");
		}
	}
}

class Element<T> implements Comparable<Element<T>> {
	T t = null;
	int distance = 0;
	ArrayList<Element<T>> nexts = new ArrayList<Element<T>>();
	Element<T> pre = null;
	boolean visited = false;

	Element(T t, int d) {
		this.t = t;
		this.distance = d;
	}

	void addNext(Element<T> next) {
		this.nexts.add(next);
	}

	@Override
	public int compareTo(Element<T> o) {
		return this.distance - o.distance;
	}
}

Code: 
a (0)
e <- a (3)
b <- a (1)
c <- b <- a (3)
d <- c <- b <- a (4)

"Unschöne" Stelle: + distances[getInx(element1.t)][getInx(element2.t)];.

@Mark 1912 bei fragen einfach fragen...
 
Vielen Dank für die viele ausführliche Hilfe, Tobias!
Aber bekomme ich mit dem Dijkstra auch den nächstgelegenen Knoten zu einem bestimmten Knoten heraus?
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Graphen: Anzahl Knoten // Knoten in Array speichern
Antworten: 4
Dijkstra Algorithmus gesucht
Antworten: 4
Dijkstra-Algorithmus
Antworten: 2
PriorityQueue im dijkstra Algorithmus implementieren
Antworten: 4
Algorithmus von Dijkstra
Antworten: 2

Zurück
Oben