找到2個節點之間的最小距離

任何人都可以幫我弄清楚如何解決我的問題。我需要找到2個給定節點之間的最短路徑。到目前爲止，我已經設法將所有可能的路徑保存在列表中，現在我試圖找到最小距離。這裏是我的代碼：找到2個節點之間的最小距離

public class A { 
    private static int[][] adjacency = new int [6][6]; 
    static int n = 6; 
    private static final int START = 1; 
    private static final int END = 4; 

    private Map<Integer, LinkedHashSet<Integer>> map = new HashMap(); 
    private Map<Integer, List<Integer>> pathsFound = new HashMap(); 

    public void addEdge(int node1, int node2) { 
     LinkedHashSet<Integer> adjacent = map.get(node1); 
     if(adjacent==null) { 
      adjacent = new LinkedHashSet(); 
      map.put(node1, adjacent); 
     } 
     adjacent.add(node2); 
    } 

    public LinkedList<Integer> adjacentNodes(Integer last) { 
     LinkedHashSet<Integer> adjacent = map.get(last); 
     if(adjacent==null) { 
      return new LinkedList(); 
     } 
     return new LinkedList<Integer>(adjacent); 
    } 

    public static void main(String[] args) { 

     LinkedList<Integer> visited = new LinkedList<Integer>(); 
     visited.add(START); 
     A graph = new A(); 

     for (int i=0;i<n;i++) 
      for (int j=0;j<n;j++) 
       adjacency[i][j] = 0;  
     adjacency[0][1] = 1; 
     adjacency[0][2] = 2; 
     adjacency[1][0] = 1; 
     adjacency[1][3] = 5; 
     adjacency[1][4] = 9; 
     adjacency[1][5] = 6; 
     adjacency[2][0] = 2; 
     adjacency[2][4] = 7; 
     adjacency[2][5] = 2; 
     adjacency[3][1] = 5; 
     adjacency[4][1] = 9; 
     adjacency[4][2] = 7; 
     adjacency[4][5] = 1; 
     adjacency[5][1] = 6; 
     adjacency[5][2] = 2; 
     adjacency[5][4] = 1; 

     graph.addEdge(0,1); 
     graph.addEdge(0,2); 
     graph.addEdge(1,0); 
     graph.addEdge(1,3); 
     graph.addEdge(1,4); 
     graph.addEdge(1,5); 
     graph.addEdge(2,0); 
     graph.addEdge(2,4); 
     graph.addEdge(2,5); 
     graph.addEdge(3,1); 
     graph.addEdge(4,1); 
     graph.addEdge(4,2); 
     graph.addEdge(4,5); 
     graph.addEdge(5,1); 
     graph.addEdge(5,2); 
     graph.addEdge(5,4); 

     graph.breadthFirst(visited); 
    } 

    public void breadthFirst(LinkedList<Integer> visited) { 
    LinkedList<Integer> nodes = adjacentNodes(visited.getLast()); 
    List<List<Integer>> allPaths = new ArrayList<List<Integer>>(); 
    List<Integer> distances = new ArrayList<Integer>(); 

    for (int node : nodes) { 
     if (visited.contains(node)) 
      continue; 
     if (node == END) { 
      visited.add(node); 
      List<Integer> path = getPath(visited); 
      System.out.println(path); 
      ??allPaths.add(path); 
      visited.removeLast(); 
      break; 
     } 
    } 

    for (int node : nodes) { 
     if (visited.contains(node) || node == END) 
      continue; 
     visited.addLast(node); 
     breadthFirst(visited); 
     visited.removeLast(); 
    } 
    System.out.println(allPaths.get(0)); 

    } 


     public static List<Integer> getPath(LinkedList<Integer> visited) { 
     List<Integer> path = new ArrayList<Integer>(); 
     for (int node : visited) 
      path.add(node); 
     return path;  
     } 

}

如果我不喜歡這個System.out.println(path);它打印的路徑，這意味着功能getPath()作品。但是，當我想把這個路徑放在一個列表中：allPaths.add(path);出了點問題，因爲當我在for循環結束後調用System.out.println(allPaths.get(0));時，我得到一個IndexOutOfBoundException。我真的不明白爲什麼我的allPaths列表是空的...

來源

2014-03-28 user3421241

你可能想要讀入djikstra的算法來獲得更高效的解決方案。 –

絕對檢查出一些算法。至於你爲什麼會得到一個IndexOutOfBoundException，這是因爲在第三次通過breadthFirst時你沒有距離元素。把你的代碼放到一個IDE中，然後用調試器遍歷代碼，或者將這個添加包裝到一個空列表的檢查中。 –

爲什麼不迭代一個foreach？

for (int number : arrlist) { 
    System.out.println("Number = " + number); 
}

來源

2014-03-28 21:57:18

我不明白你想說什麼。 – user3421241

難道你不說爲了讓你的應用程序崩潰嗎？ –

其實崩潰的應用程序是這個min = distance.get（0）。似乎沒有任何東西。我不明白爲什麼我的距離是空的 – user3421241

你也許調用的最後一個片段（你的問題）您填寫的距離收集過嗎？你需要在之後調用它，而不是之前。

[另：未來，如果您有異常，您確實需要提供異常消息和堆棧跟蹤。使你更容易...]

來源

2014-03-28 22:08:09 cybersam

找到2個節點之間的最小距離

回答

相關問題