Đường ngắn nhất (các nút ít nhất) cho biểu đồ không có trọng số

Question

Tôi đang cố gắng tạo phương thức trả về đường đi ngắn nhất từ ​​nút này đến nút khác trong biểu đồ không có trọng số. Tôi đã xem xét việc sử dụng Dijkstra nhưng điều này có vẻ hơi quá mức vì tôi chỉ muốn một đôi. Thay vào đó, tôi đã thực hiện tìm kiếm theo chiều rộng, nhưng vấn đề là danh sách trả lại của tôi chứa một số nút mà tôi không muốn - làm cách nào tôi có thể sửa đổi mã của mình để đạt được mục tiêu?

public List<Node> getDirections(Node start, Node finish){ 
    List<Node> directions = new LinkedList<Node>(); 
    Queue<Node> q = new LinkedList<Node>(); 
    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

Thực tế mã của bạn sẽ không hoàn thành trong biểu đồ tuần hoàn, hãy xem biểu đồ 1 -> 2 -> 1. Bạn phải có một số mảng nơi bạn có thể gắn cờ nút nào bạn đã truy cập. Và cũng cho mỗi nút bạn có thể lưu các nút trước đó, từ đó bạn đến. Vì vậy, đây là mã chính xác:

 
private Map<Node, Boolean>> vis = new HashMap<Node, Boolean>(); 

private Map<Node, Node> prev = new HashMap<Node, Node>(); 

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

Answer 2

Mỗi lần qua vòng lặp của bạn, bạn gọi

directions.Add(current); 

Thay vào đó, bạn nên di chuyển đến một nơi mà bạn thực sự biết bạn muốn mục đó.

Answer 3

Thực sự không có câu trả lời nào chỉ cho một cặp so với tất cả các cặp. Cách thông thường để tính toán đường đi ngắn nhất là bắt đầu giống như bạn làm, nhưng hãy ghi chú bất cứ khi nào bạn gặp một nút mới và ghi lại nút trước đó trên đường dẫn. Sau đó, khi bạn đạt đến nút đích, bạn có thể theo các liên kết ngược tới nguồn và lấy đường dẫn. Vì vậy, loại bỏ các directions.add(current) từ vòng lặp, và thêm mã giống như sau

Map<Node,Node> backlinks = new HashMap<Node,Node>(); 

ngay từ đầu và sau đó trong vòng lặp

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

và sau đó cuối cùng, chỉ cần xây dựng danh sách directions trong ngược lại bằng cách sử dụng bản đồ backlinks.

Answer 4

Bạn phải bao gồm nút cha cho mỗi nút khi bạn đặt chúng trên hàng đợi của mình. Sau đó, bạn chỉ có thể đệ quy đọc đường dẫn từ danh sách đó.

Giả sử bạn muốn tìm ra con đường ngắn nhất từ ​​A đến D trong Graph này:

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

Mỗi khi bạn enqueue một nút, theo dõi cách bạn có ở đây. Vì vậy, trong bước 1 B (A) E (A) được đặt trên hàng đợi. Trong bước hai B được dequeued và C (B) được đặt trên hàng đợi vv. Sau đó của nó dễ dàng để tìm theo cách của bạn trở lại một lần nữa, bởi chỉ cần đệ quy "ngược".

Cách tốt nhất có thể là tạo một mảng miễn là có các nút và giữ liên kết ở đó, (đó là những gì thường được thực hiện trong ví dụ. Dijkstra's).

Answer 5

Cảm ơn bạn Giolekva!

tôi viết lại nó, refactoring một số:

• Bộ sưu tập của các nút đến thăm không phải là một bản đồ.
• Để xây dựng lại đường dẫn, nút tiếp theo có thể được tra cứu, thay vì nút trước đó, loại bỏ nhu cầu đảo ngược chỉ đường.

public List<Node> getDirections(Node sourceNode, Node destinationNode) { 
    //Initialization. 
    Map<Node, Node> nextNodeMap = new HashMap<Node, Node>(); 
    Node currentNode = sourceNode; 

    //Queue 
    Queue<Node> queue = new LinkedList<Node>(); 
    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<Node> visitedNodes = new HashSet<Node>(); 
    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<Node> directions = new LinkedList<Node>(); 
    for (Node node = sourceNode; node != null; node = nextNodeMap.get(node)) { 
     directions.add(node); 
    } 

    return directions; 
}