找到两点之间的最短路径（bfs）

2 回答

• 1

  我使用了递归，其中所有答案都将存储在arrayList中 .

  getPath（int from，int to，int current，String answer）

  • 来自 - 一个起点

  • 到 - 结束点

  • current - 只是一个当前值

  • 回答 - 整个路径

  只需将此代码添加到Graph类即可 .

  public ArrayList<String> answers = new ArrayList<String>();
  
  public void printShortAnswer() {
      String realAnswer = "";
      for (String answer : answers) {
          if (realAnswer == "" || realAnswer.length() > answer.length()) {
              realAnswer = answer;
          }
      }
      System.err.println("The shortest path is: " + realAnswer);
  }
  
  //store all answers in answers
  public boolean getPath(int from, int to, int current, String answer) {
      boolean visited[] = new boolean[V];
      visited[from] = true;
      visited[current] = true;
  
      if (current == to) {
           answers.add(answer);
          return true;
      }
  
      Iterator<Integer> i = adj[current].listIterator();
      while (i.hasNext())
      {
          int n = i.next();
          if (!visited[n])
          {
              visited[n] = true;
              getPath(from, to, n, answer + " " + n);
          }
      }
      return false;
  }
  

  要运行它，只需使用此设置

  Graph g = new Graph(12);
      g.addEdge(0, 1);
      g.addEdge(0, 2);
  
      //set 1
      g.addEdge(1, 3);
      g.addEdge(3, 4);
      g.addEdge(4, 5);
  
      //set 2
      g.addEdge(2, 8);
      g.addEdge(8, 9);
      g.addEdge(9, 11);
      g.addEdge(11, 5);
  
      g.addEdge(0, 5);
      //g.BFS(0);
  
      int startPoint = 0;
      g.getPath(startPoint, 5, startPoint, startPoint + " ");
      g.printShortAnswer();
  

  并且不要忘记导入ArrayList .

  import java.util.ArrayList;
  

  输出将是：

  • 0 1 3 4 5

  • 0 2 8 9 11 5

  • 0 5

  • 最短路径为：0 5

  回复于 2024-04-19T09:38:14+08:00
• 3

  广度优先搜索在这里是合适的，因为当您第一次访问目标节点时，您将通过最短路径进行搜索 . 这是有效的，因为所有边都具有相同的权重，1 . 如果边可以具有不同的权重，则具有最少边的路径不一定是最短的路径，并且您将需要其他算法，例如Dijkstra's .

  您的代码不会检查您是否已到达目的地;它只是以breadh-first顺序访问所有节点 .

  您也无法随意打印节点，因为当您访问相邻的未访问节点时，您还不知道它是否是最短路径的一部分，或者您是否朝着错误的方向前进 .

  对此的解决方案是为每个顶点存储前一个顶点，即您来自的顶点 . 例如，如果在顶点0处开始搜索，则将访问相邻的顶点5和7.因此，5和7的前一个顶点都是0 .

  此信息可以执行双重任务：如果使用-1表示“无顶点”，则前一个顶点-1表示尚未访问该顶点 .

  当您访问目的地时，只需通过先前节点的信息回溯您的步骤，直到您到达原始顶点 . 此列表将是从目标到原点的路径 .

  这是（我的可怜）Java中的实现：

  import java.util.LinkedList;
  import java.util.Iterator;
  
  class Graph
  {
      private int V;   
      private LinkedList<Integer> adj[];
  
      Graph(int v)
      {
          V = v;
          adj = new LinkedList[v];
  
          for (int i = 0; i < v; i++) {
              adj[i] = new LinkedList();
          }
      }
  
      void addEdge(int v, int w)
      {
          adj[v].add(w);
      }
  
      LinkedList shortest(int from, int to)
      {
          LinkedList<Integer> queue = new LinkedList<Integer>();
          LinkedList<Integer> res = new LinkedList<Integer>();
  
          int prev[] = new int[V];
  
          if (from == to) return res;
          queue.add(from);
  
          for (int i = 0; i < V; i++) {
              prev[i] = -1;
          }        
  
          while (queue.size() != 0) {
              int curr = queue.poll();
              Iterator<Integer> i = adj[curr].listIterator();
  
              while (i.hasNext()) {
                  int n = i.next();
  
                  if (prev[n] == -1) {                // unvisited?
                      prev[n] = curr;                 // store previous vertex
  
                      if (n == to) {                  // we're finally there!
                          while (n != from) {         // build result list ...
                              res.addFirst(n);
                              n = prev[n];
                          }
  
                          return res;                 // ... and return it
                      }                    
  
                      queue.add(n);
                  }
              }
          }
  
          return res;
      }
  
      public static void main(String args[])
      {
          Graph g = new Graph(9);
  
          g.addEdge(0, 5);
          g.addEdge(0, 7);
          g.addEdge(1, 5);
          g.addEdge(1, 4);
          g.addEdge(1, 2);
          g.addEdge(2, 1);
          g.addEdge(2, 4);
          g.addEdge(2, 3);
          g.addEdge(3, 4);
          g.addEdge(3, 2);
          g.addEdge(4, 5);
          g.addEdge(4, 1);
          g.addEdge(4, 2);
          g.addEdge(4, 3);
          g.addEdge(5, 0);
          g.addEdge(5, 1);
          g.addEdge(5, 4);
          g.addEdge(6, 7);
          g.addEdge(7,6);
          g.addEdge(7,0);
  
          for (int a = 0; a < 9; a++) {
              System.out.print("--- ");
              System.out.println(a);
  
              for (int b = 0; b < 9; b++) {
                  System.out.println(g.shortest(a, b));                
              }
          }    
      }
  }
  

  回复于 2024-04-19T09:38:14+08:00