2016-05-13 17 views
2

Ich habe ein Problem bei der Umwandlung von Pseudocode des Dijkstras-Algorithmus in tatsächlichen Code festgestellt. Ich wurde gegeben und Adjazenzliste wie "Standort - Nachbarstandort - Entfernung zum Standort", Beispiel für einen Knoten: AAA AAC 180 AAD 242 AAH 40. Meine Aufgabe war es, eine Datei als Adjacency-Liste wie beschrieben organisiert zu lesen, und berechnen Sie die kürzester Weg von einem Knoten zum anderen. Hier ist der Dijkstra Pseudo-Code:Dijkstra Adjazenzliste

void dijkstra(Vertex s) 
    { 
     for each Vertex v 
     { 
      v.dist = INFINITY; 
      v.known = false; 
     } 
     s.dist = 0; 
     while(there is an unknown distance vertex) 
     { 
      Vertex v = smallest unknown distance vertex; 
      v.known = true; 

     for each Vertex w adjacent to v 
      if(!w.known) 
      { 
      DistType cvw = cost of edge from v to w; 
      if(v.dist + cvw < w.dist) 
      { 
    // Update w 
      decrease(w.dist to v.dist + cvw); 
      w.path = v; 
      } 
      } 
      } 
    } 

im die meisten Probleme mit der Zeile "für jeden Vertex w neben v" Hier hat mein arbeitsfreien Code:

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.ListIterator; 

public class Dijkstra { 

    public static boolean isInteger(String s) { 
     return isInteger(s, 10); 
    } 

    public static boolean isInteger(String s, int radix) { 
     if (s.isEmpty()) 
      return false; 
     for (int i = 0; i < s.length(); i++) { 
      if (i == 0 && s.charAt(i) == '-') { 
       if (s.length() == 1) 
        return false; 
       else 
        continue; 
      } 
      if (Character.digit(s.charAt(i), radix) < 0) 
       return false; 
     } 
     return true; 
    } 

    public static void dijkstra(Vertex[] a, Vertex s, int lineCount) { 
     int i = 0; 
     while (i < (lineCount)) // each Vertex v 
     { 
      a[i].dist = Integer.MAX_VALUE; 
      a[i].known = false; 
      i++; 
     } 

     s.dist = 0; 
     int min = Integer.MAX_VALUE; // 

     while (!(a[0].known == true && a[1].known == true && a[2].known == true && a[3].known == true 
       && a[4].known == true && a[5].known == true && a[6].known == true && a[7].known == true 
       && a[8].known == true && a[9].known == true && a[10].known == true && a[11].known == true 
       && a[12].known == true)) { 
      System.out.println("here"); 
      for (int b = 0; b < lineCount; b++) { 

       if (a[b].dist < min && a[b].known == false) { 
        min = a[b].dist; 
       } 
      } 
      int c = 0; 
      while (c < lineCount) { 

       if (a[c].dist == min && a[c].known == false) { 
        break; 
       } 
       c++; 
      } 
      System.out.println(min); 

      a[c].known = true; 
      int adjSize = a[c].adj.size(); 

      int current = 0; 

      System.out.println(adjSize); 

      while (current < adjSize - 1) { 

       String currentAdjacent = (String) a[c].adj.get(current); 
       int p = 0; 

       while (p < lineCount) { 
        if (a[p].name.equals(currentAdjacent)) { 

         if (!a[p].known) { 
          String cvwString = (String) a[c].distance.get(current); 
          int cvw = Integer.parseInt(cvwString); 
          System.out.println(" This is cvw" + cvw); 
          System.out.println("Here2"); 

          if (a[c].dist + cvw < a[p].dist) { 
           a[p].dist = a[c].dist + cvw; 
           a[p].path = a[c]; 
          } 
         } 
        } 
        p++; 
       } 
       current++; 
      } 
     } 
    } 

    public static class Vertex { 
     public List adj; // Adjacency list 
     public List distance; 
     public boolean known; 
     public int dist; // DistType is probably int 
     public Vertex path; 
     public String name; 

     // Other fields and methods as needed 
    } 

    public static void printPath(Vertex v) { 
     if (v.path != null) { 
      printPath(v.path); 
      System.out.print(" to "); 
     } 
     System.out.print(v); 
    } 

    public static void main(String[] args) throws IOException { 

     int lineCounter = 0; 

     BufferedReader br = new BufferedReader(new FileReader("airport.txt")); 
     try { 
      StringBuilder sb = new StringBuilder(); 
      String line = br.readLine(); 

      while (line != null) { 

       sb.append(line); 
       sb.append(System.lineSeparator()); 
       line = br.readLine(); 

       lineCounter = lineCounter + 1; 
      } 

      Vertex[] arr = new Vertex[lineCounter]; 
      for (int i = 0; i < lineCounter; i++) { 
       arr[i] = new Vertex(); 
       arr[i].adj = new LinkedList<String>(); 
       arr[i].distance = new LinkedList<Integer>(); 
      } 
      ; 

      // 
      int arrayCounter = 0; 
      String everything = sb.toString(); 
      String[] lines = everything.split("\\s*\\r?\\n\\s*"); 

      for (String line1 : lines) { 
       arr[arrayCounter] = new Vertex(); 

       arr[arrayCounter].adj = new LinkedList<String>(); 
       arr[arrayCounter].distance = new LinkedList<Integer>(); 
       String[] result = line1.split("\\s+"); 

       for (int x = 0; x < result.length; x++) { 
        if (x == 0) { 
         arr[arrayCounter].name = result[0]; 
         continue; 
        } else if (isInteger(result[x])) { 
         arr[arrayCounter].distance.add(result[x]); 
         continue; 
        } else { 
         arr[arrayCounter].adj.add(result[x]); 
         continue; 
        } 
       } 

       arrayCounter++; 
      } 

      for (int i = 0; i < 12; i++) { 
       System.out.println(arr[i].name); 
      } 
      System.out.println(lineCounter); 
      dijkstra(arr, arr[3], lineCounter - 1); 
      printPath(arr[11]); 

     } finally { 
      br.close(); 
     } 
    } 
} 

Mit meiner Vertex-Klasse als Wenn ich zuerst eine Reihe von while-Schleifen verwende, durchquere ich die Adjazenz-Strings, die in einer verketteten Liste gespeichert sind, während ich vergleiche, um zu sehen, welcher Scheitelpunkt der Adjazenzlisten-Zeichenkette entspricht. Gibt es eine bessere Möglichkeit zum Codieren "für jeden Vertex w neben v" mithilfe meiner Vertex-Klasse? Und ich entschuldige mich für chaotischen Code und andere Sünden, die ich vielleicht begangen habe. Vielen Dank!

+2

Verschachtelte Strukturen ohne Einrückung machen Code fast unlesbar. Bitte beachten Sie, dass Sie die Formatierung des ersten Codeblocks korrigieren müssen. – ChiefTwoPencils

+0

Ok, sollte jetzt besser formatiert sein. – panzerschwein

+0

Warum implementieren Sie 'isInteger' nicht einfach mit' s.matches ("^ -? [0-9] +") '? Warum musst du das Radix beachten? (Du gibst nie irgendwas außer 10, implizit) –

Antwort

1

Um dieses Problem zu lösen, benötigen Sie eine Reihe von "Node" -Objekten, die in einer HashMap gespeichert sind und am Source Location verschlüsselt sind.

Im Knoten benötigen Sie eine Sammlung von Referenzen zu benachbarten "Node" -Objekten (oder zumindest deren "Schlüssel", sodass Sie eine Logik dagegen schreiben können. Der "Node" muss auch seinen Standort und seine Entfernung kennen "Angrenzender" Knoten Think Lundon U-Bahn Tube Maps - jede Station verbindet sich mit mindestens einer anderen Station. In der Regel zwei oder mehr. Daher sind benachbarte Knoten zu U-Bahn-Stationen die unmittelbaren nächsten Haltestellen, die Sie von dieser Station aus erreichen können.

Sobald Sie diese Datenstruktur an Ort und Stelle haben, können Sie dann eine rekursive Routine verwenden, um jeden einzelnen Knoten zu durchlaufen.Sie sollte dann durch jeden untergeordneten Knoten (auch bekannt als benachbarter Knoten) iterieren und Abstände vom ursprünglichen Knoten (Quelle) zum aktuellen verfolgen Knoten, indem Sie diese Daten in einer HashMap speichern und den aktuellen Akku verwenden Distanz während des Wiederholens (oder "Gehens" des Graphen). Diese Verfolgungsinformationen sollten bei der Rekursion Teil Ihrer Methodensignatur sein. Sie müssen auch den aktuellen Pfad verfolgen, den Sie bei der Rekursion genommen haben, um Kreisschleifen zu vermeiden (was letztlich und ironischerweise einen StackOverflowError verursachen wird). Sie können dies tun, indem Sie ein HashSet verwenden. Dieser Satz sollte die Position des Quell- und aktuellen Knotens als Eingabe-Schlüssel verfolgen. Wenn Sie das während Ihrer Rekursion sehen, dann haben Sie es schon gesehen, also fahren Sie nicht weiter.

Ich werde nicht die Lösung für Sie kodieren, weil ich vermute, dass Sie spezifischere Fragen stellen, während Sie Ihren Weg durch das Verständnis der Antwort, die sehr wahrscheinlich anderswo beantwortet werden.