如何表示一个无权有向图并找到最短路径？ 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)。启发式值越接近实际的移动次数，算法越快