1

過去 2 日間から、グラフの最長パスを計算するためのロジックを見つけようとしています。DAG で簡単に見つけることができ、一般に多項式時間アルゴリズムであることがわかっています。正式には、最長パスを計算するためのヒューリスティックを実装したいと思います。さらに、グラフにエッジが存在する確率 p が与えられている場合、どのように問題を解決できますか..ヘルプ...

4

4 に答える 4

2

私の知る限り、最長パスの計算は多項式時間ではできません。最長パス アルゴリズムの Java 実装に従うと、特定のソースの正の加重グラフの最長パスが検出されますが、最悪の場合は指数関数的な時間がかかります。

public class LongestPath {
static int times;
public double initLongestPath(ArrayList<Vertex> V,Vertex source){
    for(Vertex u:V){
        u.setVisited(false);
    }
    return getLongestPath(source);
}
public double getLongestPath(Vertex v){
    ++times;
    System.out.println(times);
    double w,dist,max=0;
    v.setVisited(true);
    for(Edge e:v.getOutGoingEdges()){
        if(!e.getToNode().isVisited()){
            dist=e.getWeight()+getLongestPath(e.getToNode());
            if(dist>max)
                max=dist;
        }
    }

    v.setVisited(false);    
    return max;
}

}

于 2013-05-29T08:43:53.720 に答える
-2

常に幅優先検索(BFS) を使用することができます。グラフにエッジを追加するときはいつでも、加法逆数 (乗算すると -1) としてコストがかかります。このようにして、最長のエッジを使用して「最短経路」を見つけます。スカラー変換を行っているため、グループ内で追加する機能を失うことはありません (乗法逆数を使用すると失われます)。

于 2011-11-08T19:39:56.257 に答える
-3

パスの重みを反転し、最短パス アルゴリズムを実行します。得られる最小の数値 (最も負の数値) が最長のパスです。

于 2011-11-08T15:33:24.193 に答える