如何表示一個無權有向圖並找到最短路徑？ Java

Question

在Java中表示圖形的最佳方式是什麼？我這樣做：

public class Node<T> { 
public T data; 
public LinkedList<Node> children; 
public Node(T data) { 
    this.data = data; 
    this.children = new LinkedList<Node>(); //here there are the connected nodes of the node 
} 

public T getData() { 
    return this.data; 
} 
public void addArch(Node n) { 
    children.add(n); 
} 


public class Graph <T> { 
private Node<T> source = new Node(null); 
private Node<T> target = new Node(null); 
private ArrayList<Node> nodes = new ArrayList<Node>(); 

public Graph() {} 
public void addNode(T v) { 
    boolean visto = false; 
    for (Node n: nodes) { 
     if (n.getData().equals(v)) { 
      visto = true; 
     } 
    } 
    if (visto == false) { 
     nodes.add(new Node(v)); 
    } 
} 
public void addEdge(T p, T a) throws NoSuchNodeException { 
    boolean visto = false; 
    boolean visto_secondo = false; 
    for (Node n: nodes) { 
     if (n.getData().equals(p)) { 
      visto = true; 
     } 
    } 
    for (Node n: nodes) { 
     if (n.getData().equals(a)) { 
      visto_secondo = true; 
     } 
    } 
    if (visto == false || visto_secondo == false) { 
     throw new NoSuchNodeException(); 
    } 
    else { 
     for (Node n : nodes) { 
      if (p.equals(n.getData())) { 
       System.out.print(a); 

       n.addArch(new Node(a)); 
      } 
     } 
    } 

} 

我必須找到最短的路徑，但它似乎沒有添加弓，爲什麼？我也做了一套並獲得源和目標。然而，我必須找到這個源和目標之間的最短路徑，使用什麼算法？我需要使用bfs來獲得最短路徑，但是我的問題是如何迭代arch，我需要做一個遞歸函數我認爲

Answer 1

查找到目標節點的最短路徑的最佳算法是Iterative Deepening A*。

它發現到目標節點的最短路徑，只要啓發式值是可接受的，這意味着它不會高估。

這裏是僞代碼：

node    current node 
g     the cost to reach current node 
f     estimated cost of the cheapest path (root..node..goal) 
h(node)   estimated cost of the cheapest path (node..goal) 
cost(node, succ) step cost function 
is_goal(node)  goal test 
successors(node) node expanding function, expand nodes ordered by g + h(node) 

procedure ida_star(root) 
    bound := h(root) 
    loop 
    t := search(root, 0, bound) 
    if t = FOUND then return bound 
    if t = ∞ then return NOT_FOUND 
    bound := t 
    end loop 
end procedure 

function search(node, g, bound) 
    f := g + h(node) 
    if f > bound then return f 
    if is_goal(node) then return FOUND 
    min := ∞ 
    for succ in successors(node) do 
    t := search(succ, g + cost(node, succ), bound) 
    if t = FOUND then return FOUND 
    if t < min then min := t 
    end for 
    return min 
end function 

的g表示的移動的數目以獲得當前的狀態和h表示的估計數目的移動到達目標狀態。 f := g + h(node)。啓發式值越接近實際的移動次數，算法越快