未加权图的最短路径（最少节点）

我正在尝试构建一个方法，在未加权的图形中返回从一个节点到另一个节点的最短路径。 我考虑过使用Dijkstra，但这似乎有点矫枉过正，因为我只想要一对。 相反，我已经实现了广度优先搜索，但问题是我的返回列表包含一些我不想要的节点 – 如何修改我的代码以实现我的目标？

public List getDirections(Node start, Node finish){ List directions = new LinkedList(); Queue q = new LinkedList(); Node current = start; q.add(current); while(!q.isEmpty()){ current = q.remove(); directions.add(current); if (current.equals(finish)){ break; }else{ for(Node node : current.getOutNodes()){ if(!q.contains(node)){ q.add(node); } } } } if (!current.equals(finish)){ System.out.println("can't reach destination"); } return directions; } 

Answer 1

实际上你的代码不会在循环图中完成，考虑图1 – > 2 – > 1.你必须有一个数组，你可以标记你已访问过哪个节点。 并且对于每个节点，您可以保存之前的节点。 所以这里是正确的代码：

 private Map > vis = new HashMap （）;

 private Map  prev = new HashMap （）;

 public List getDirections（节点开始，节点完成）{
    列出方向= new LinkedList（）;
    队列q = new LinkedList（）;
    节点电流=开始;
     q.add（电流）;
     vis.put（当前，真实）;
    而（！q.isEmpty（））{
         current = q.remove（）;
         if（current.equals（finish））{
            打破;
         }其他{
             for（Node node：current.getOutNodes（））{
                如果（！vis.contains（节点））{
                     q.add（节点）;
                     vis.put（node，true）;
                     prev.put（节点，当前）;
                 }
             }
         }
     }
     if（！current.equals（finish））{
         System.out.println（“无法到达目的地”）;
     }
     for（Node node = finish; node！= null; node = prev.get（node））{
         directions.add（节点）;
     }
     directions.reverse（）;
    返回方向;
 }

Answer 2

谢谢Giolekva！

我重写了它，重构了一些：

• 受访节点的集合不必是地图。
• 对于路径重建，可以查找下一个节点，而不是前一个节点，从而无需反转方向。

 public List getDirections(Node sourceNode, Node destinationNode) { //Initialization. Map nextNodeMap = new HashMap(); Node currentNode = sourceNode; //Queue Queue queue = new LinkedList(); queue.add(currentNode); /* * The set of visited nodes doesn't have to be a Map, and, since order * is not important, an ordered collection is not needed. HashSet is * fast for add and lookup, if configured properly. */ Set visitedNodes = new HashSet(); visitedNodes.add(currentNode); //Search. while (!queue.isEmpty()) { currentNode = queue.remove(); if (currentNode.equals(destinationNode)) { break; } else { for (Node nextNode : getChildNodes(currentNode)) { if (!visitedNodes.contains(nextNode)) { queue.add(nextNode); visitedNodes.add(nextNode); //Look up of next node instead of previous. nextNodeMap.put(currentNode, nextNode); } } } } //If all nodes are explored and the destination node hasn't been found. if (!currentNode.equals(destinationNode)) { throw new RuntimeException("No feasible path."); } //Reconstruct path. No need to reverse. List directions = new LinkedList(); for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) { directions.add(node); } return directions; } 

Answer 3

获得单对的答案并不比简单的所有对更简单。 计算最短路径的常用方法是像您一样开始，但每当遇到新节点时记录并记录路径上的上一个节点。 然后，当您到达目标节点时，您可以跟踪到源的反向链接并获取路径。 因此，从循环中删除directions.add(current) ，并添加如下代码

 Map backlinks = new HashMap(); 

在开始然后在循环中

 if (!backlinks.containsKey(node)) { backlinks.add(node, current); q.add(node); } 

然后最后，使用backlinks映射向后构建directions列表。

Answer 4

每次通过你的循环，你都会打电话

 directions.Add(current); 

相反，你应该把它移到你真正知道你想要那个条目的地方。

Answer 5

将它们放入队列时，必须将父节点包含在每个节点中。 然后，您可以递归地从该列表中读取路径。

假设您要在此图中找到从A到D的最短路径：

  /B------C------D / | A / \ / \E--------- 

每次排队节点时，都要跟踪到达此处的方式。 因此，在步骤1 B（A）中，E（A）被放入队列中。 在第二步中，B出队，C（B）被放入队列等。然后通过“向后”递归，很容易找到回来的路。

最好的方法可能是制作一个数组，只要有节点并保持链接在那里（这通常是在Dijkstra’s中完成的）。