Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen

Mark 1912 · 19. Jun 2019

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);
   
    }

Xyz1 · 19. Jun 2019

Nimm a*.

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

Demzufolge wäre deins falsch...

Mark 1912 · 20. Jun 2019

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;
    }

Mark 1912 · 20. Jun 2019

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
       
    }

   


}

Mark 1912 · 20. Jun 2019

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).

Xyz1 · 20. Jun 2019

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.

Mark 1912 · 20. Jun 2019

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)              
           
            }
     }

Xyz1 · 20. Jun 2019

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

Xyz1 · 21. Jun 2019

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

Mark 1912 · 27. Jun 2019

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?

Xyz1 · 27. Jun 2019

Si, Du bekommst alle nächstgelegenen Knoten heraus. Das sind Knoten deren Pfad die Länge 1 hat.

mihe7 · 27. Jun 2019

Mark 1912 hat gesagt.:
Aber bekomme ich mit dem Dijkstra auch den nächstgelegenen Knoten zu einem bestimmten Knoten heraus?

Die bekommst Du auch ohne Dijkstra raus. Dazu schaust Du einfach alle ausgehenden Kanten des Knotens an und nimmst die mit der geringsten Entfernung.

	Titel	Forum	Antworten	Datum
D	Dijkstra Algorithmus Hilfe!!	Java Basics - Anfänger-Themen	9	18. Sep 2021
U	Meinung zum Dijkstra Algorithmus	Java Basics - Anfänger-Themen	6	25. Mai 2020
U	Dijkstra Algorithmus Laufzeit	Java Basics - Anfänger-Themen	3	24. Mai 2020
S	Dijkstra Algorithmus funktioniert nicht	Java Basics - Anfänger-Themen	4	16. Jun 2018
S	GraphNode --- Dijkstra Algorithmus : NullPointerException	Java Basics - Anfänger-Themen	1	23. Jan 2015
B	PriorityQueue im dijkstra Algorithmus implementieren	Java Basics - Anfänger-Themen	4	2. Dez 2010
W	Dijkstra im Graph	Java Basics - Anfänger-Themen	18	30. Jul 2024
S	Dijkstra-Algoritmus	Java Basics - Anfänger-Themen	7	10. Mrz 2020
	Tipp für Ein-/Ausgabe für Dijkstra	Java Basics - Anfänger-Themen	6	19. Jun 2011
K	Dijkstra implementierung 2.0	Java Basics - Anfänger-Themen	19	16. Jun 2011
T	Dijkstra auf adjazenzmatrix	Java Basics - Anfänger-Themen	7	1. Okt 2007
K	Algorithmus entwickeln	Java Basics - Anfänger-Themen	1	22. Apr 2024
	Eigenschaften eines Algorithmus (determiniert vs.. deterministisch)	Java Basics - Anfänger-Themen	2	10. Mrz 2023
C	Gewinnspiel erstellen mit Algorithmus	Java Basics - Anfänger-Themen	3	31. Jan 2023
C	negamax-Algorithmus für Tic-Tac-Toe spielt manchmal falsch	Java Basics - Anfänger-Themen	10	12. Jan 2023
H	Minimax Algorithmus in Tic Tac Toe	Java Basics - Anfänger-Themen	3	12. Jan 2023
M	Minimax-Algorithmus für Vier gewinnt	Java Basics - Anfänger-Themen	11	21. Dez 2022
	Trockentest Algorithmus, mathematischen Zusammenhang angeben	Java Basics - Anfänger-Themen	3	19. Dez 2022
M	Minimax-Algorithmus	Java Basics - Anfänger-Themen	17	22. Sep 2022
	Binary Search Algorithmus ausführen	Java Basics - Anfänger-Themen	1	3. Sep 2022
J	Rekursiver Algorithmus	Java Basics - Anfänger-Themen	9	1. Sep 2022
M	monte carlo Algorithmus für 4 gewinnt	Java Basics - Anfänger-Themen	12	1. Aug 2022
	Sortier Algorithmus für Bounding Box Elememte Links nach Rechts und von Oben nach Unten	Java Basics - Anfänger-Themen	33	7. Jul 2022
S	Algorithmus entwicklen, der zu einem gegebenen Datum die Jahreszeit ermittelt	Java Basics - Anfänger-Themen	13	13. Mai 2022
	Merge-Algorithmus	Java Basics - Anfänger-Themen	53	12. Mai 2022
C	Ein Algorithmus soll schneller werden	Java Basics - Anfänger-Themen	24	29. Dez 2021
U	Den Kuchen aufteilen - aber wie? (Rebalancing-Algorithmus)	Java Basics - Anfänger-Themen	14	6. Aug 2021
	Pseudocode Naiver Algorithmus	Java Basics - Anfänger-Themen	17	16. Jul 2021
H	String verschlüsseln - eigener Algorithmus	Java Basics - Anfänger-Themen	104	5. Jul 2021
T	Algorithmus für Index mit min-Wert	Java Basics - Anfänger-Themen	2	1. Jul 2021
	Testen meines Algorithmus	Java Basics - Anfänger-Themen	1	19. Jun 2021
D	Primzahlen Rechner nach Eratostenes von Kyrene Algorithmus	Java Basics - Anfänger-Themen	2	31. Mai 2021
	Frage zum Euklidischen Algorithmus	Java Basics - Anfänger-Themen	11	22. Mai 2021
S	Algorithmus java searchAll IKey	Java Basics - Anfänger-Themen	4	4. Mai 2021
S	Algorithmus Datensätze einfügen wenn...	Java Basics - Anfänger-Themen	26	30. Apr 2021
	MergeSort Algorithmus	Java Basics - Anfänger-Themen	2	24. Apr 2021
	Textdatei einlesen im Array (Selection Sort Algorithmus)	Java Basics - Anfänger-Themen	3	22. Apr 2021
	Compiler-Fehler Algorithmus zur Bestimmung von Primzahlen	Java Basics - Anfänger-Themen	7	15. Apr 2021
S	Algorithmus (reelle Zahl <65536 von dezimal zu dual) max. 10 Nachkommastellen	Java Basics - Anfänger-Themen	4	6. Apr 2021
G	Algorithmus Graphen	Java Basics - Anfänger-Themen	10	18. Mrz 2021
D	Input/Output fehlerhafter Algorithmus zum Ersetzen von Array-Werten nach logischem Schema	Java Basics - Anfänger-Themen	1	12. Dez 2020
N	Selection Algorithmus: Methode wird nicht erkannt (BlueJ)	Java Basics - Anfänger-Themen	3	3. Sep 2020
L	Math.exp also eigenen Algorithmus	Java Basics - Anfänger-Themen	2	3. Apr 2020
	Algorithmus entwickeln	Java Basics - Anfänger-Themen	37	16. Jan 2020
M	Algorithmus Max-Heap?	Java Basics - Anfänger-Themen	3	27. Dez 2019
I	Labyrinth auf der Basis eines rekursiven Algorithmus	Java Basics - Anfänger-Themen	27	15. Dez 2019
	Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren	Java Basics - Anfänger-Themen	3	13. Dez 2019
A	Algorithmus effizienter machen	Java Basics - Anfänger-Themen	1	30. Nov 2019
V	Algorithmus zur fortlaufenden Berechnung des duechscjnt	Java Basics - Anfänger-Themen	1	31. Okt 2019
O	Labyrinth Algorithmus	Java Basics - Anfänger-Themen	3	6. Mai 2019
G	Quicksort Algorithmus	Java Basics - Anfänger-Themen	12	30. Apr 2019
S	Binäre-Suche Algorithmus	Java Basics - Anfänger-Themen	1	29. Apr 2019
D	Algorithmus in Pseudocode mit log2(n) Operationen erstellen	Java Basics - Anfänger-Themen	3	22. Apr 2019
C	Laufzeit eines Sortier-Algorithmus ermitteln	Java Basics - Anfänger-Themen	4	8. Apr 2019
H	aufgabe java luhn algorithmus	Java Basics - Anfänger-Themen	10	1. Apr 2019
A	Datenstruktur für Savings Algorithmus und Planung von kleinen Programmierprojekten	Java Basics - Anfänger-Themen	1	11. Dez 2018
J	Algorithmus für eine Reihe implementieren	Java Basics - Anfänger-Themen	2	13. Okt 2018
N	Denksportaufgabe durch Algorithmus lösen	Java Basics - Anfänger-Themen	2	12. Apr 2018
S	Problem mit einem rekursivem FloodFill Algorithmus	Java Basics - Anfänger-Themen	62	11. Jan 2018
B	Algorithmus Square und Multiply	Java Basics - Anfänger-Themen	3	3. Jan 2018
J	Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen	Java Basics - Anfänger-Themen	4	14. Jun 2017
D	Frage Boyer-Moore Algorithmus	Java Basics - Anfänger-Themen	7	5. Jun 2017
M	Komplexität Algorithmus	Java Basics - Anfänger-Themen	8	9. Mai 2017
H	Zeichen im algorithmus	Java Basics - Anfänger-Themen	4	9. Mrz 2017
B	Code Verständnisfragen - FLoyd Warshall Algorithmus	Java Basics - Anfänger-Themen	1	9. Feb 2017
B	Algorithmus zum entmischen einer Zahlenfolge	Java Basics - Anfänger-Themen	15	30. Nov 2016
X	Minimax-Algorithmus über alle Kanten möglich? - Kanten darstellen	Java Basics - Anfänger-Themen	1	5. Nov 2016
T	Algorithmus zur Überprüfung eines binären Suchbaums	Java Basics - Anfänger-Themen	2	29. Apr 2016
K	Best Practice Algorithmus für Berechnung von Zahlenreihenfolge	Java Basics - Anfänger-Themen	12	17. Mrz 2016
M	Simpler Algorithmus läuft extrem langsam.	Java Basics - Anfänger-Themen	3	5. Dez 2015
K	Erste Schritte Brute Force Algorithmus	Java Basics - Anfänger-Themen	2	4. Nov 2015
L	Frage zu BubbleSort Algorithmus	Java Basics - Anfänger-Themen	2	10. Okt 2015
B	gibt es ein Stundenplan-Algorithmus?	Java Basics - Anfänger-Themen	11	21. Aug 2015
O	Algorithmus-Problem	Java Basics - Anfänger-Themen	5	10. Aug 2015
P	Euklidischer Algorithmus	Java Basics - Anfänger-Themen	9	19. Jun 2015
L	Greates Commong Dividend - euklidischer Algorithmus, modulos not positive	Java Basics - Anfänger-Themen	5	28. Apr 2015
J	Euklidischer Algorithmus	Java Basics - Anfänger-Themen	1	11. Apr 2015
S	Quicksort Algorithmus	Java Basics - Anfänger-Themen	2	8. Apr 2015
B	Rekursive Algorithmus schreiben	Java Basics - Anfänger-Themen	8	7. Dez 2014
V	Algorithmus in einer Methode ausführen	Java Basics - Anfänger-Themen	3	1. Dez 2014
M	Implementierung des Knuth-Morris-Pratt-Algorithmus	Java Basics - Anfänger-Themen	0	23. Sep 2014
M	Dijkstras Algorithmus	Java Basics - Anfänger-Themen	5	13. Sep 2014
S	Zusammenhang Datenstruktur/Algorithmus	Java Basics - Anfänger-Themen	1	25. Jun 2014
M	Simulation - Algorithmus	Java Basics - Anfänger-Themen	3	23. Jun 2014
F	Erste Schritte Hilfe beim Algorithmus finden	Java Basics - Anfänger-Themen	8	6. Jun 2014
D	Algorithmus für Punkte auf einem Kreis	Java Basics - Anfänger-Themen	0	20. Mai 2014
D	Algorithmus zu gegebener Laufzeit implementieren	Java Basics - Anfänger-Themen	1	24. Apr 2014
B	Doppelte Werte aus Array entfernen ohne Import - Algorithmus	Java Basics - Anfänger-Themen	5	10. Mrz 2014
C	Ideen für einen Algorithmus	Java Basics - Anfänger-Themen	1	8. Jan 2014
F	Best Practice Algorithmus optimieren - Binaeruhr	Java Basics - Anfänger-Themen	2	21. Nov 2013
S	Euklid Algorithmus zur Berechnung des GGTs	Java Basics - Anfänger-Themen	2	29. Sep 2013
L	Welcher Algorithmus ist das ?	Java Basics - Anfänger-Themen	9	17. Dez 2012
J	Rekursiver Horner-Schema-Algorithmus - Verstehe ich ihn richtig?	Java Basics - Anfänger-Themen	2	11. Dez 2012
O	Java Zufalls-Verteil-Algorithmus	Java Basics - Anfänger-Themen	3	14. Nov 2012
P	ganz simpler algorithmus	Java Basics - Anfänger-Themen	3	4. Nov 2012
C	Sortieren ohne Algorithmus	Java Basics - Anfänger-Themen	8	1. Nov 2012
J	Algorithmus: Grad von floating zu Grad/Minute/Sekunde	Java Basics - Anfänger-Themen	3	18. Okt 2012
A	Text Verschriebung/Algorithmus(?)	Java Basics - Anfänger-Themen	8	21. Jun 2012
R	Rekursionsformel für Laufzeit von Algorithmus	Java Basics - Anfänger-Themen	3	20. Mai 2012
E	Algorithmus für kart. Produkt: als int [] Feld repräsentiert	Java Basics - Anfänger-Themen	10	5. Mrz 2012

Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen

Mark 1912

Mitglied

Xyz1

Gast

Mark 1912

Mitglied

Mark 1912

Mitglied

Mark 1912

Mitglied

Xyz1

Gast

Mark 1912

Mitglied

Xyz1

Gast

Xyz1

Gast

Mark 1912

Mitglied

Xyz1

Gast

mihe7

Top Contributor

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen