最小前綴/所有節點圖形算法的後綴

Question

我有以下結構圖

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

現在我們定義A1的後綴：

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

，最小值爲：

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

例如：

條

鑑於3條無環路徑{A3-A4-A1, A4-A1, A5-A1}，在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]} 

注意，邊沿值可以是負也。

問：
我需要找到min(S(A(i)))爲圖中的所有節點i。

對於在時間複雜度方面最好的方法是什麼？

Answer 1

您可以使用基本深度優先搜索來查找最小值。

這是主要的示例圖。

在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)); 
    } 
}