有向图的邻接表

Question

我正在开发一个实现 Dijkstra 最短路径算法的程序。它从文本文件中的邻接表输入开始，格式为：

模式顶点名adj.vertex权重adj.vertex权重.....

我找到了一些示例代码，可以像这样填充图表：

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

这可行，除了，如我所说，我需要从格式类似于上述文件的文本文件中填充此数据。我运行遇到的麻烦是每行的数据量没有设定限制。一个节点可以有一个或无限多个其他节点附加到它。我正在尝试提出一个能够解决这个问题的解决方案。到目前为止，我在我的主要方法中进行了粗略的尝试：

Scanner scanner = new Scanner(new File(filename));
    while(scanner.hasNextInt()){
        String source = scanner.next();
        String to = scanner.next();
        int weight = scanner.nextInt();
        Graph.Edge edge = new Graph.Edge(source, to, weight);
        if(scanner.hasNext()){
            to = scanner.next();
            weight = scanner.nextInt();
            Graph.Edge edge2 = new Graph.Edge(source, to, weight);
        }
    }

当我尝试运行这个程序时，我在 Scanner.throwfor、Scanner.next 和我的主 class 中的这一行得到了 NoSuchElementException：

String to = scanner.next();

我知道我的尝试目前在语法上并不完全正确，但我是否在寻找解决方案的正确道路上？另外，有什么关键的东西我正在查看或者会让这更容易吗？谢谢！

编辑：这是我从 http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java

开始的代码的 link

Answer 1

[编辑]

这是一个代码片段，它将用 Edges 实例填充 ArrayList：

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

try {
    Scanner scanner = new Scanner(new File(filepath));
    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 (Exception e) {
    e.printStackTrace();
}

它使用hasNextLine和findInLine一次处理一条线，以确保正确创建具有相同source值的边。

NAME 和 WEIGHT 模式由这些常量定义：

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

有向图的邻接表

Adjacency List to Directed Graph

java

graph

dijkstra

nodes