Нахождение кратчайшего пути узлов с широтой первого поиска

Question

Я бег широты первым поиска на графику выше, чтобы найти кратчайший путь от Node 0 к Node 6.

Мой код

public List<Integer> shortestPathBFS(int startNode, int nodeToBeFound){ 
     boolean shortestPathFound = false; 
     Queue<Integer> queue = new LinkedList<Integer>(); 
     Set<Integer> visitedNodes = new HashSet<Integer>(); 
     List<Integer> shortestPath = new ArrayList<Integer>(); 
     queue.add(startNode); 
     shortestPath.add(startNode); 

     while (!queue.isEmpty()) { 
      int nextNode = queue.peek(); 
      shortestPathFound = (nextNode == nodeToBeFound) ? true : false; 
      if(shortestPathFound)break; 
      visitedNodes.add(nextNode); 
      System.out.println(queue); 
      Integer unvisitedNode = this.getUnvisitedNode(nextNode, visitedNodes); 

      if (unvisitedNode != null) { 
        queue.add(unvisitedNode); 
        visitedNodes.add(unvisitedNode); 
        shortestPath.add(nextNode); //Adding the previous node of the visited node 
        shortestPathFound = (unvisitedNode == nodeToBeFound) ? true : false; 
        if(shortestPathFound)break; 
       } else { 
        queue.poll(); 
       } 
     } 
     return shortestPath; 
    } 

мне нужно отслеживать узлы, через которые BFS Algo. пройденный для достижения узла 6, например [0,3,2,5,6]. Для этого я создал список с именем shortestPath &, пытающийся сохранить предыдущие узлы посещенных узлов, чтобы получить список узлов. Referred

Но это не работает. Самый короткий путь [0,3,2,5,6]

В списке, что я получаю это Shortest path: [0, 0, 0, 0, 1, 3, 3, 2, 5]

Это отчасти верно, но дает дополнительные 1.

Если бы я снова начать с первым элементом 0 из shortestPath списка & начать обход & откатов. Нравится 1 не имеет края 3, поэтому я возвращаюсь назад & переезд из 0 в 3 в 5, я получу ответ, но не уверен, что это правильный путь.

Каков идеальный способ получить узлы для кратчайшего пути?

Answer 1

Хранение всех посещенных узлов в одном списке не помогает найти самый короткий путь, потому что в конце концов вы не знаете, какие узлы были теми, которые привели к целевому узлу, а какие были тупиками.

Что нужно сделать: для каждого узла для хранения предыдущего узла в пути от исходного узла.

Таким образом, создать карту Map<Integer, Integer> parentNodes, и вместо этого:

shortestPath.add(nextNode); 

сделать это:

parentNodes.put(unvisitedNode, nextNode); 

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

if(shortestPathFound) { 
    List<Integer> shortestPath = new ArrayList<>(); 
    Integer node = nodeToBeFound; 
    while(node != null) { 
     shortestPath.add(node) 
     node = parentNodes.get(node); 
    } 
    Collections.reverse(shortestPath); 
} 

Answer 2

В дополнение к уже предоставленному нам ответу er3290797.

Похоже, вы имеете дело с невзвешенным графиком. Мы интерпретируем это так, что каждое ребро имеет вес 1. В этом случае, если вы связали расстояние с корневым узлом с каждым узлом графа (первым обходным путем), становится тривиально восстанавливать кратчайший путь от любого узел, и даже определить, если их несколько.

Все, что вам нужно сделать - это ширина (в случае, если вы хотите получить кратчайший путь) или обход глубины одного и того же графа, начиная с целевого узла, и только учитывая, что соседи имеют значение глубины ровно на 1 меньше.

Таким образом, нам нужно прыгать с расстояния 4 (узел 6) до 3, 2, 1, 0, и есть только один способ (в данном случае) сделать это.

В случае, если нас интересует кратчайший путь к узлу 4, результатом будут расстояния 2-1-0 или узлы 4-3-0 или 4-8-0.

BTW, этот подход может быть легко изменен для работы с взвешенными графиками (с неотрицательными весами) тоже: действительными соседями являются те, у которых расстояние равно текущему минус весу края - это связано с некоторыми фактическими расчетами и непосредственно сохранение предыдущих узлов вдоль кратчайшего пути может быть лучше.

Answer 3

Как вы можете видеть в acheron55 answer:

«Это имеет чрезвычайно полезное свойство, что, если все ребра в графе являются невзвешенная (или тот же вес), то первый раз посещают узел кратчайший путь к этому узлу от исходного узла «

Итак, все, что вам нужно сделать, - отслеживать путь, по которому цель была достигнута. Простой способ сделать это - нажать на Queue весь путь, используемый для достижения узла, а не самого узла.
Преимущество этого в том, что, когда цель достигнута, очередь удерживает путь, используемый для ее достижения.
Вот простая реализация:

/** 
* unlike common bfs implementation queue does not hold a nodes, but rather collections 
* of nodes. each collection represents the path through which a certain node has 
* been reached, the node being the last element in that collection 
*/ 
private Queue<List<Node>> queue; 

//a collection of visited nodes 
private Set<Node> visited; 

public boolean bfs(Node node) { 

    if(node == null){ return false; } 

    queue = new LinkedList<>(); //initialize queue 
    visited = new HashSet<>(); //initialize visited log 

    //a collection to hold the path through which a node has been reached 
    //the node it self is the last element in that collection 
    List<Node> pathToNode = new ArrayList<>(); 
    pathToNode.add(node); 

    queue.add(pathToNode); 

    while (! queue.isEmpty()) { 

     pathToNode = queue.poll(); 
     //get node (last element) from queue 
     node = pathToNode.get(pathToNode.size()-1); 

     if(isSolved(node)) { 
      //print path 
      System.out.println(pathToNode); 
      return true; 
     } 

     //loop over neighbors 
     for(Node nextNode : getNeighbors(node)){ 

      if(! isVisited(nextNode)) { 
       //create a new collection representing the path to nextNode 
       List<Node> pathToNextNode = new ArrayList<>(pathToNode); 
       pathToNextNode.add(nextNode); 
       queue.add(pathToNextNode); //add collection to the queue 
      } 
     } 
    } 

    return false; 
} 

private List<Node> getNeighbors(Node node) {/* TODO implement*/ return null;} 

private boolean isSolved(Node node) {/* TODO implement*/ return false;} 

private boolean isVisited(Node node) { 
    if(visited.contains(node)) { return true;} 
    visited.add(node); 
    return false; 
} 

Это также применимо к циклическим графах, где узел может иметь более одного родителя.