定向圖的鄰接列表

Question

我正在研究一個實現Dijkstra最短路徑算法的程序。它從鄰接表中的文本文件輸入，格式爲：

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

與vertexname 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和我的主類中在這條線得到NoSuchElementException異常：

String to = scanner.next(); 

我知道我的嘗試目前沒有完全的語法正確，但我是否找到找到解決方案的正確途徑？另外，有沒有我正在查找的關鍵字，或者會讓這更容易？謝謝！

編輯：這裏是鏈接到我開始http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java

Answer 1

將帖子代碼

下面的代碼片段，將在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+");