Реализация алгоритма Дейкстры с использованием прямых графиков

Question

Я пытаюсь реализовать алгоритм Дейкстры, используя ориентированный граф через список смежности. Я нашел пример кода, который я использовал в качестве примера. В этом коде, график заполняется следующим образом:

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

Поскольку мне нужно заполнить из списка смежности в виде текстового файла, вместо этого я пытался сделать это таким образом:

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

с

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

В примере кода, они затем запустить алгоритм Дейкстры на графике следующим образом:

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

Я попытался обновить свой код для работы над этой реализацией алгоритма. Я придумал следующее:

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

Когда я пытаюсь запустить это, кажется, что неправильно заполняет мой график. Он создает ошибки из метода dijkstra и printPath, говорящие, что «График не содержит начальную/конечную вершину». Как я могу обновить свой код, чтобы график был правильно заполнен и смог правильно реализовать алгоритм? Благодаря!

EDIT: Вот пример моего входного файла

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

вытекает источник формата, прил. вершина, вес, прил. вершина, вес ....

EDIT 2: Использование 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; 
    } 
} 

и

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: Вот где я нашел оригинальный образец кода от http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java

Answer 1

Чтобы использовать приложение с вводом файла, используйте свой первый алгоритм ввода файлов. Второй алгоритм бесполезен, если вы не хотите запускать каждую строку файла как Graph только с одним Vertex.

Используйте свой код, как это (я положил комментарии на линии я изменил):

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 
} 

Затем запустите приложение таким же образом:

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

я тестировал все из этого, а также обнаружили, что ваш алгоритм для ввода файла разбивается на последнюю строку файла, поэтому я добавил if (scanner.hasNextLine()) до scanner.nextLine();