2

次の構造のグラフがあります

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

例：

{A3-A4-A1, A4-A1, A5-A1}A1 で終わる3 つの非循環パスがあると、次のようになります。

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]}

Edge の値は負の値にもなり得ることに注意してください。

質問:グラフ内のすべてのノード
を検索する必要があります。min(S(A(i)))i

時間の複雑さの観点から、それを行うための最良の方法は何ですか?

4

1 に答える 1

0

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

これはメインのグラフの例です。 ここに画像の説明を入力

ジャバで…

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));
    }
}
于 2016-08-02T07:17:58.347 に答える