Implementierung des Dijkstra-Algorithmus unter Verwendung gerichteter Graphen

Question

Ich versuche den Dijkstra-Algorithmus unter Verwendung eines gerichteten Graphen über eine Adjazenzliste zu implementieren. Ich habe einen Beispielcode gefunden, den ich als Beispiel benutzt habe. In diesem Code wird das Diagramm wie folgt aufgefüllt:

private static final Graph.Edge[] GRAPH = { 
    new Graph.Edge("a", "b", 7), 
    new Graph.Edge("a", "c", 9), 
    new Graph.Edge("a", "f", 14), 
    new Graph.Edge("b", "c", 10), 
    new Graph.Edge("b", "d", 15), 
    new Graph.Edge("c", "d", 11), 
    new Graph.Edge("c", "f", 2), 
    new Graph.Edge("d", "e", 6), 
    new Graph.Edge("e", "f", 9),}; 
private static final String START = "a"; 
private static final String END = "e"; 

Da ich aus einer Adjazenzliste in einer Textdatei füllen müssen, stattdessen habe ich versucht, es auf diese Weise zu tun:

List<Graph.Edge> list = new ArrayList<>(); 

    try { 
     Scanner scanner = new Scanner(new File(filename)); 
     while (scanner.hasNextLine()) { 
      String source = scanner.findInLine(NAME); 
      if (source != null) { 
       while (true) { 
        String to = scanner.findInLine(NAME); 
        if (to == null) { 
         break; 
        } 
        int weight = Integer.valueOf(scanner.findInLine(WEIGHT)); 
        list.add(new Graph.Edge(source, to, weight)); 
       } 
      } 
      scanner.nextLine(); 
     } 
    } catch (FileNotFoundException | NumberFormatException e) { 
    } 

mit

static final Pattern NAME = Pattern.compile("\\w+"); 
static final Pattern WEIGHT = Pattern.compile("\\d+"); 

in dem Beispielcode, laufen sie dann Dijkstra-Algorithmus auf dem Graphen in folgenden Weise:

Graph g = new Graph(GRAPH); 
    g.dijkstra(START); 
    g.printPath(END); 
    g.printAllPaths(); 

Ich habe versucht, meinen Code für diese Implementierung des Algorithmus zu aktualisieren. Ich kam mit der folgenden auf:

try { 
     Scanner scanner = new Scanner(new File(filename)); 

     while (scanner.hasNextLine()) { 
      String source = scanner.findInLine(NAME); 
      if (source != null) { 
       while (true) { 
        String go = scanner.findInLine(NAME); 
        if (go == null) { 
         break; 
        } 
        int weight = Integer.valueOf(scanner.findInLine(WEIGHT)); 
        Graph.Edge edge = new Graph.Edge(source, go, weight); 

        Graph g = new Graph(GRAPH); 
        g.dijkstra(source); 
        g.printPath(go); 
       } 
      } 

      scanner.nextLine(); 
     } 
    } catch (FileNotFoundException | NumberFormatException e) { 
    } 

Wenn ich versuche, und diese laufen, es scheint nicht richtig mein Diagramm zu füllen. Es erzeugt die Fehler von der Dijkstra und PrintPath-Methode, die besagt, dass "Graph Start/End-Vertex nicht enthält". Wie kann ich meinen Code aktualisieren, damit der Graph korrekt ausgefüllt wird und der Algorithmus korrekt implementiert werden kann? Vielen Dank!

EDIT: Hier ist ein Beispiel meiner Eingabedatei

1 2 1 3 1 
2 4 2 
3 2 2 5 4 
4 3 3 5 3 
5 1 4 

Es folgt das Format Quelle, adj. Scheitelpunkt, Gewicht, adj. Scheitel, Gewicht ....

EDIT 2: Verwendung von Graph.Edge`

class Graph { 

private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges 

/** 
* One edge of the graph (only used by Graph constructor) 
*/ 
public static class Edge { 

    public final String v1, v2; 
    public final int dist; 

    public Edge(String v1, String v2, int dist) { 
     this.v1 = v1; 
     this.v2 = v2; 
     this.dist = dist; 
    } 
} 

und

public Graph(Edge[] edges) { 
    graph = new HashMap<>(edges.length); 

    //one pass to find all vertices 
    for (Edge e : edges) { 
     if (!graph.containsKey(e.v1)) { 
      graph.put(e.v1, new Vertex(e.v1)); 
     } 
     if (!graph.containsKey(e.v2)) { 
      graph.put(e.v2, new Vertex(e.v2)); 
     } 
    } 

    //another pass to set neighbouring vertices 
    for (Edge e : edges) { 
     graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist); 
     //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph 
    } 
} 

EDIT: Hier ist, wo ich den ursprünglichen Beispielcode aus http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java

gefunden

Answer 1

Um die Anwendung mit Dateieingabe zu verwenden, verwenden Sie Ihren ersten Dateieingabealgorithmus. Ihr zweiter Algorithmus ist nutzlos, wenn Sie nicht jede Zeile der Datei als Graph mit nur einem Vertex ausführen möchten.

Verwenden Sie Ihren Code wie folgt (Ich habe auf den Linien setzen Kommentare, die ich geändert haben):

private static final Graph.Edge[] GRAPH = getEdges("input.txt"); // <-- CHANGED THIS 
private static final String START = "1"; // <-- CHANGED THIS 
private static final String END = "5"; // <-- CHANGED THIS 

private static Graph.Edge[] getEdges(String fileName) { // <-- ADDED THIS 
    final Pattern NAME = Pattern.compile("\\w+"); 
    final Pattern WEIGHT = Pattern.compile("\\d+"); 
    List<Graph.Edge> list = new ArrayList<>(); 
    try { 
     Scanner scanner = new Scanner(new File(fileName)); 
     while (scanner.hasNextLine()) { 
      String source = scanner.findInLine(NAME); 
      if (source != null) { 
       while (true) { 
        String to = scanner.findInLine(NAME); 
        if (to == null) { 
         break; 
        } 
        int weight = Integer.valueOf(scanner.findInLine(WEIGHT)); 
        list.add(new Graph.Edge(source, to, weight)); 
       } 
      } 
      if (scanner.hasNextLine()) // <-- ADDED THIS 
       scanner.nextLine(); 
     } 
    } catch (FileNotFoundException | NumberFormatException e) { 
    } 
    return list.toArray(new Graph.Edge[0]); // <-- ADDED THIS 
} 

Dann führen Sie die Anwendung auf die gleiche Weise:

Graph g = new Graph(GRAPH); 
g.dijkstra(START); 
g.printPath(END); 
g.printAllPaths(); 

ich alle getestet von diesem, und auch festgestellt, dass Ihr Algorithmus für die Dateieingabe in der letzten Zeile der Datei bricht, so fügte ich if (scanner.hasNextLine()) vor scanner.nextLine();