Probleme mit Dijkstra Java Code

Question

Probleme mit Dijkstra Algorithmus,

Versuchen, Pfade zwischen zwei Städten zu erhalten.

Hier sind meine Java-Klassen ...

Die ConnectedVertices Klasse ist, wo die vertice Array ist ...

ich eine Arraylist verwendet, um Städte Verbindungen zwischen

zu erzeugen

package main; 

public class Edges 
{ 
    public String u; 
    public String v; 
    public String d; 

    public Edges(String city1, String city2, String distance) 
    { 
     u = city1; 
     v = city2; 
     d = distance; 
    } 
    public Edges(int city1, int city2, int distance) 
    { 
     u = String.valueOf(city1); 
     v = String.valueOf(city2); 
     d = String.valueOf(distance); 
    } 
} 

hier die Vertices und die Arraylist repräsentieren den Graphen.

package main; 

import java.util.ArrayList; 
import java.util.PriorityQueue; 
import java.util.List; 
import java.util.Collections; 
import org.apache.commons.lang3.ArrayUtils; 

public class ConnectedVertices 
{ 
    public String[] vertice = { "lagos", "ikeja", "Benin city", "Agbor", "Sagamu", "Ibadan", 
         "Iwo", "Osogbo", "Abuja", "Kafanchan", "Jos", "Bauchi", "Gombe", 
         "Biu", "N’djamena", "Dikwa", "Maiduguri", "Damaturu", "Potiskum", 
         "Azare", "Dutse", "Wudil", "Kano", "Kusada", "Chafe", "Gusau", 
         "Talata-Mafara", "Kaduna", "Zaria", "Ikire", "Ondo", "Sapele", "Warri", 
         "Yenegoa", "Portharcourt", "Aba", "Ikot-ekpene", "Oturkpo", "Makurdi", 
         "Idah", "Lokoja", "Abaji", "Umuahia", "Owerri", "Akwa", "Damboa", 
         "Egbe-ejiba", "katsina", "Sokoto", "Ore", "Calabar", "Agbor", "Onitsha", 
         "Lafia", "Enugu"}; 

    //public ArrayList<Edges> edges = new ArrayList(); 
    ArrayList<Edges> edges = new ArrayList<Edges>(); 

    public ConnectedVertices() 
    { 
     AddEdges(); 
    } 

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

    } 

    @SuppressWarnings("unchecked") 
public void AddEdges() 
    { 
     edges.add(new Edges(0, 1, 46)); 
     edges.add(new Edges(1, 4, 55)); 
     edges.add(new Edges(1, 2, 304)); 
     edges.add(new Edges(2, 49, 107)); 
     edges.add(new Edges(2, 31, 63)); 
     edges.add(new Edges(2, 3, 70)); 
     edges.add(new Edges(3, 51, 79)); 
     edges.add(new Edges(4, 5, 84)); 
     edges.add(new Edges(5, 6, 46)); 
     edges.add(new Edges(5, 29, 31)); 
     edges.add(new Edges(6, 7, 48)); 
     edges.add(new Edges(7, 46, 154)); 
     edges.add(new Edges(8, 46, 388)); 
     edges.add(new Edges(8, 9, 171)); 
     edges.add(new Edges(8, 27, 187)); 
     edges.add(new Edges(9, 10, 110)); 
     edges.add(new Edges(10, 11, 130)); 
     edges.add(new Edges(10, 52, 206)); 
     edges.add(new Edges(11, 12, 157)); 
     edges.add(new Edges(12, 13, 126)); 
     edges.add(new Edges(13, 45, 101)); 
     edges.add(new Edges(14, 15, 177)); 
     edges.add(new Edges(15, 16, 142)); 
     edges.add(new Edges(16, 17, 133)); 
     edges.add(new Edges(17, 18, 99)); 
     edges.add(new Edges(18, 19, 148)); 
     edges.add(new Edges(19, 20, 106)); 
     edges.add(new Edges(20, 21, 77)); 
     edges.add(new Edges(21, 22, 38)); 
     edges.add(new Edges(22, 23, 112)); 
     edges.add(new Edges(22, 24, 245)); 
     edges.add(new Edges(23, 47, 94)); 
     edges.add(new Edges(24, 25, 41)); 
     edges.add(new Edges(25, 26, 95)); 
     edges.add(new Edges(26, 48, 111)); 
     edges.add(new Edges(27, 28, 80)); 
     edges.add(new Edges(27, 8, 185)); 
     edges.add(new Edges(27, 10, 217)); 
     edges.add(new Edges(28, 22, 157)); 
     edges.add(new Edges(29, 30, 109)); 
     edges.add(new Edges(30, 49, 96)); 
     edges.add(new Edges(31, 32, 40)); 
     edges.add(new Edges(32, 33, 137)); 
     edges.add(new Edges(33, 34, 116)); 
     edges.add(new Edges(34, 35, 61)); 
     edges.add(new Edges(35, 36, 41)); 
     edges.add(new Edges(36, 50, 109)); 
     edges.add(new Edges(36, 42, 50)); 
     edges.add(new Edges(37, 38, 109)); 
     edges.add(new Edges(37, 53, 156)); 
     edges.add(new Edges(38, 52, 101)); 
     edges.add(new Edges(39, 51, 142)); 
     edges.add(new Edges(39, 40, 122)); 
     edges.add(new Edges(40, 41, 88)); 
     edges.add(new Edges(41, 8, 113)); 
     edges.add(new Edges(42, 53, 126)); 
     edges.add(new Edges(43, 51, 42)); 
     edges.add(new Edges(43, 34, 106)); 
     edges.add(new Edges(44, 51, 46)); 
     edges.add(new Edges(44, 53, 129)); 
     edges.add(new Edges(45, 16, 88)); 
     System.out.println("Contents of all locations: " + edges.size()); 
    } 

    public String Connected(String first, String second) 
    { 
     int p,a; 
     for (int i = 1; i <= edges.size(); i++) { 
      for (int j = 0; j < edges.size(); j++) { 
      //this is as far i could go... 
     } 
     } 


    } 

} 

Bitte brauchen Hilfe ...

Answer 1

Sie benötigen ein wenig mehr Erklärung des Algorithmus Ich denke:

int p,a; 
    for (int i = 1; i <= edges.size(); i++) { 
     for (int j = 0; j < edges.size(); j++) { 
     //this is as far i could go... 
    } 
    } 

zuerst die Wiki-Seite mit Beispiel-Code lesen:

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Und dann schauen Sie (es eine Warteschlange verwenden), ich Ich kann den Code nicht kopieren, er hat keine Lizenz. Bitte folgen Sie dem Link,

https://github.com/iensen/Algorithms/blob/master/Graphs/Djikstra.java