algorithm - 所有节点图算法的最小前缀/后缀

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

示例:

给定三个以 A1 结尾的非循环路径 {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));
    }
}