3

私はグラフの問題をより良く解こうとして、過去数年間の ACM プログラミング コンペティションの問題に取り組んでいます。

私が現在取り組んでいるのは、任意の数の無向グラフ ノード、それらの隣接ノード、およびノー​​ドを接続するエッジの距離が与えられていることです。私が必要とするのは、互いに最も遠い2つのノード間の距離です(ノードの数ではなく、重みの距離です)。

今、私はダイクストラのアルゴリズムを次の形式で持っています:

// Dijkstra's Single-Source Algorithm
private int cheapest(double[] distances, boolean[] visited)
{
        int best = -1;
        for (int i = 0; i < size(); i++)
        {
                if (!visited[i] && ((best < 0) || (distances[i] < distances[best])))
                {
                        best = i;
                }
        }
        return best;
}

// Dijkstra's Continued
public double[] distancesFrom(int source)
{
        double[] result = new double[size()];
        java.util.Arrays.fill(result, Double.POSITIVE_INFINITY);
        result[source] = 0; // zero distance from itself
        boolean[] visited = new boolean[size()];
        for (int i = 0; i < size(); i++)
        {
                int node = cheapest(result, visited);
                visited[node] = true;
                for (int j = 0; j < size(); j++)
                {
                        result[j] = Math.min(result[j], result[node] + getCost(node, j));
                }

        }
        return result;
}

この実装では、特定のノードを与えることができ、そのノードからのすべての距離のリストが表示されます。したがって、その距離のリストで最大の距離を取得できますが、特定のノードがどちらかの端にある 2 つの最も遠いノードの 1 つであるかどうかはわかりません。

したがって、私が考えることができる唯一の解決策は、このダイクストラのアルゴリズムをすべてのノードで実行し、返された距離の各リストを調べて、最大の距離を探すことです。距離のリストを返す各ノードを使い果たした後、任意の 2 つのノード間の最大距離の値が必要です (2 つの最も広く離れた村の間の「道路」距離)。これは非常に計算コストがかかるように思われるため、これを行うためのより簡単な方法が必要です。問題は、最大 500 ノードのサンプル入力が存在する可能性があることを示しているため、非常に長くかかることは望ましくありません。これは私がそれを行うべき方法ですか？

問題のサンプル入力は次のとおりです。

合計ノード: 5

エッジ:
ノード 2 - 接続 - ノード 4. 距離/重量 25
ノード 2 - 接続 - ノード 5. 距離/重量 26
ノード 3 - 接続 - ノード 4. 距離/重量 16
ノード 1 - 接続 - ノード 4. 距離/重量 14

この入力例の答えは「67 マイル」です。これは、最も離れた 2 つの村の間の道路の長さです。

それで、私が説明した方法でそれを行うべきですか、それとももっと簡単で計算コストの低い方法がありますか?

4

6 に答える 6

3

次のいずれかを使用できるようです。

私は専門家ではありませんが、それらについて多くのガイダンスを提供することはできません。

于 2008-10-04T06:05:53.813 に答える
2

したがって、O(VlogV + E) を実行する Dijkstra の実装があり、おおよそ V^2logV + VE の複雑なアプローチになります。DADSを参照してください。しかし、 Floyd-Warshall や Johnsons などの全ペア最短パスアルゴリズムのいずれかを実行する方が、おそらくより直感的です。残念ながら、密なグラフの場合、それらはすべておおよそ O(V^3) です (E = V^2 の完全なグラフに近い)。

于 2008-10-04T06:10:03.197 に答える
1

これは北方道路の問題ですか？

于 2008-10-04T08:33:00.133 に答える
0

Dijkstra の実装は次のように使用できます。

  1. ランダムなノード (a) を選び、ノード a から Dijkstra を実行し、そこから最も遠いノードを見つけます。そのノードをノード b としてマークします。
  2. ノード b から Dijkstra を再度実行し、そこから最も遠いノードを見つけます。そのノードをノード c としてマークします。

これについての証拠はありませんが、b と c が最も遠いノードになると思います。もう一度反復を実行する必要があるかもしれません (私はまだそれについて考えています)。

于 2008-10-04T06:03:32.947 に答える
0

辺の重みに -1 を掛けて、新しいグラフで最短経路を見つけます。それは元のグラフの最長パスになります

于 2008-10-04T06:14:15.733 に答える
0

最長最短パスが必要な場合

sup i,j {inf i,j {n : n=i と j の間のパスの長さ}}

他の人が述べたように、Flyod-Warshall のようなすべてのノードの最短パス アルゴリズムを検討する必要があります。これは O(V^3) のオーダーになります。

可能な限り長いパスが必要な場合

sup i,j {n : n=i と j の間のパスの長さ}

Midhat のアイデアを使用することができます。（コメントで指摘されているように、これは実際には元の問題と同じくらい複雑です）ただし、元の重みが厳密に正であったことを考えると、正の重みを保持するために、1 / wで重みを反転することをお勧めします。

負の重みを扱うときに参照する必要がある別のアルゴリズムは、Bellman と Ford のアルゴリズムです。

于 2008-10-04T08:30:34.990 に答える