ユニエイト有向グラフを表現し、最短経路を見つける方法は？ 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を使う必要があるが、私の問題はアーチを反復する方法だと思う。私は思う再帰関数を実行する必要がある。

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)。ヒューリスティックな値が実際の移動数に近ければ近いほど、アルゴリズムは速くなります