すべてのノードのグラフアルゴリズム

Question

の最小接頭辞/接尾辞に私は今、私たちはA1の接尾辞は、以下の構造

V = {A1, A2, A3, A4, A5, .., An} 
E = {E1, E2, E3, E4, .., Ek} 

でグラフを定義しています

S(A1) = {All acyclic paths that end in A1} 

を、最小である：

min(S(A1)) = Minimum of all suffix paths of A1 

例：

次にA1で終了3つの非環状経路{A3-A4-A1, A4-A1, A5-A1}、与えられる：エッジ値が負であることができること

S(A1)[1] = Edge(A3,A4) + Edge(A4,A1) 
S(A1)[2] = Edge(A4,A1) 
S(A1)[3] = Edge(A5,A1) 

min(S(A1)) = min{S(A1)[1] ,S(A1)[2] ,S(A1)[3]} 

注意。

質問：
私は、グラフ内のすべてのノードiためmin(S(A(i)))を見つける必要があります。

時間の複雑さの点で最も良い方法は何ですか？

Answer 1

基本的な深さの最初の検索を使用して最小値を見つけることができます。

これはmainのグラフです。 Javaで

...

public class Graph { 

    class Edge{ 
     int w; 
     int v; 
     int value; 

     Edge(int v,int w,int value){ 
      this.v=v; 
      this.w=w; 
      this.value=value; 
     } 

    } 

    Graph(int V) { 
     this.V = V; 
     this.E = 0; 
     adj = (List<Integer>[]) new List[V]; 
     paths=new ArrayList<>(); 
     edges=new ArrayList<>(); 
     visited = new boolean[V]; 
     edgeTo = new int[V]; 
     for (int v = 0; v < V; v++) { 
      adj[v] = new LinkedList<>(); 

     } 
    } 


    List<Integer>[] adj; 
    ArrayList<String> paths; 
    ArrayList<Edge> edges; 
    int V; 
    int E; 
    int pathTo; 
    boolean[] visited; 
    int[] edgeTo; 



    void addEdge(int v, int w, int value) { 
     adj[v].add(w); 
     adj[w].add(v); 
     edges.add(new Edge(v,w,value)); 
     E++; 
    } 
    Edge getEdge(int v, int w){ 
     for(Edge e: edges){ 
      if(e.v==v && e.w==w || e.v==w && e.w==v) return e; 
     } 
     return new Edge(-1,-1,0);//randomly chose these values 
    } 
    void dfs(Graph G, int s) { 
     visited = new boolean[G.V]; 
     S(G, s, ""); 
    } 

    void S(Graph G, int v, String path) { 
     visited[v] = true; 
     path+=Integer.toString(v); 
     if(v == pathTo) paths.add(path); 
     for (int w : G.adj[v]) { 
      if (!visited[w]) { 
       edgeTo[w] = v; 
       S(G, w, path); 

      } 
     } 
     visited[v] = false; 
    } 

    int pathValue(String path){ 
     int result = 0; 
     for(int i=0;i<path.length()-1;i++){ 
      result+=getEdge(Character.getNumericValue(path.charAt(i)), 
        Character.getNumericValue(path.charAt(i+1))).value; 
     } 
     return result; 
    } 


    /** 
    * 
    * @param from = starting vertex 
    * @param to = end vertex 
    * @return value for the lowest cost path starting at s 
    */ 
    int minPath(Graph g, int from,int to){ 
     pathTo = to; 
     dfs(g,from); 
     int min=Integer.MAX_VALUE; 
     for(String path:g.paths){ 
      int val = g.pathValue(path); 
      if(val<min) min=val; 
     } 
     return min; 
    } 



    public static void main(String[] args) { 
     Graph g = new Graph(6); 
     g.addEdge(0,1,-1); 
     g.addEdge(1,2,7); 
     g.addEdge(1,3,6); 
     g.addEdge(0,5,3); 
     g.addEdge(5,3,4); 
     g.addEdge(2,3,5); 
     g.addEdge(4,2,8); 
     g.addEdge(4,0,2); 

     System.out.println(g.minPath(g,0,3)); 
    } 
}