3

Floyd-Warshall アルゴリズム (すべてのペアの最短パス) を実装しようとしています。以下のコードでは、いくつかの数字を入力すると、最後の数字が入力として表示されます。私はコードが完全ではないことを知っています。

各 i と j の最短パスを出力するにはどうすればよいでしょうか? または、このコードを完成させるために私に何をするように提案しますか? ありがとう。

private void button10_Click(object sender, EventArgs e)
{

    string ab = textBox11.Text;
    int matrixDimention = Convert.ToInt32(ab);
    int[,] intValues = new int[matrixDimention, matrixDimention];
    string[] splitValues = textBox9.Text.Split(',');
    for (int i = 0; i < splitValues.Length; i++)
        intValues[i / (matrixDimention), i % (matrixDimention)] =    Convert.ToInt32(splitValues[i]);
    string displayString = "";
    for (int inner = 0; inner < intValues.GetLength(0); inner++)
    {
        for (int outer = 0; outer < intValues.GetLength(0); outer++)
            displayString += String.Format("{0}\t", intValues[inner, outer]);
        displayString += Environment.NewLine;
    }
    int n = (int)Math.Pow(matrixDimention, 2);
    string strn = n.ToString();

    MessageBox.Show("matrix"+strn+ "in" + strn + "is\n\n\n" +displayString);
////before this line i wrote the codes to get the numbers that user enter in textbox and put it in an 2d array
    for (int k = 1; k < n+1; k++)

        for (int i = 1; i < n+1; i++)

            for (int j = 1; j < n+1; j++)

                if (intValues[i, j] > intValues[i, k] + intValues[k, j])
                {
                    intValues[i, j] = intValues[i, k] + intValues[k, j];
                    string str_intvalues = intValues[i, j].ToString();
                    MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);

                }
                else
                {
                    string str_intvalues = intValues[i, j].ToString();
                    MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
                }
}
4

2 に答える 2

9

同じページにいるために、最初に Floyd-Warshall アルゴリズムをお見せしましょう。

matrix で表されるグラフを考えてみましょうD。ここD[i][j]で、 はエッジの長さです(i -> j) (グラフの index の頂点から index の頂点iまでj)。

各グラフの頂点を互いに接続することでパスの最大数に到達できるため、行列Dのサイズは ですN * N。ここで、Nはグラフ内の頂点の総数です。

Rまた、最短パスを格納する matrix も必要です(頂点で始まり頂点で終わるR[i][j]、最短パスの次の頂点のインデックスを含みます)。ij

MatrixRは と同じサイズDです。

Floyd-Warshall アルゴリズムは、次の手順を実行します。

  1. エッジの終了頂点を使用して、グラフ内の任意の 2 つのペアまたは頂点間のすべてのパスのマトリックスを初期化します(この値はパスの再構築に使用されるため、これは重要です)。

  2. 接続された頂点の各ペアに対して(読み取り: 各エッジに対して(u -> v))、uおよびv、それらの間の最短経路を形成する頂点を見つけます: 頂点が2 つの有効なエッジをk定義している場合 (それらがグラフに存在する場合)、これらは合わせてより短いpathの場合、 と の間の最短経路を想定します。エッジのマトリックスの最短ピボット ポイントを、エッジの対応するピボット ポイントに設定します。(u -> k)(k -> v) (u -> v)uvkR(u -> v)(u -> k)

定義と同じページにいるので、アルゴリズムは次のように実装できます。

// Initialise the routes matrix R
for (int i = 0; i < N; i++) {
    for (int t = 0; t < N; t++) {
        R[i][t] = t;
    }
}

// Floyd-Warshall algorithm:
for (int k = 0; k < N; k++) {
    for (int u = 0; u < N; u++) {
        for (int v = 0; v < N; v++) {
            if (D[u, v] > D[u, k] + D[k, v]) {
                D[u, v] = D[u, k] + D[k, v];
                R[u, v] = R[u, k];
            }
        }
    }
}

しかし、行列をどのように読むのDでしょうか?

グラフを見てみましょう:

グラフ

GraphViz では、次のように記述されます。

digraph G {
    0->2 [label = "1"];
    2->3 [label = "5"];
    3->1 [label = "2"];
    1->2 [label = "6"];
    1->0 [label = "7"];
}

最初にサイズの 2 次元配列を作成します4 (グラフには正確に4頂点があるため)。

頂点からそれ自体への最短経路は長さを持ち、その他の要素は非常に大きな数を持つため(例えばG[0, 0]G[1, 1]エッジがないか、それらの間に無限に長いエッジがあります)。グラフのエッジに対応する定義済みの要素に、エッジの長さを入力します。0

int N = 4;
int[,] D = new int[N, N];

for (int i = 0; i < N; i++) {
    for (int t = 0; t < N; t++) {
        if (i == t) {
            D[i, t] = 0;
        } else {
            D[i, t] = 9999;
        }
    }
}

D[0, 2] = 1;
D[1, 0] = 7;
D[1, 2] = 6;
D[2, 3] = 5;
D[3, 1] = 2;

アルゴリズムの実行後、マトリックスRは頂点のインデックスで満たされ、それらの間の最短経路が記述されます。u頂点から頂点へのパスを再構築するにvは、行列の要素に従う必要がありますR。

List<Int32> Path = new List<Int32>();

while (start != end)
{
    Path.Add(start);

    start = R[start, end];
}

Path.Add(end);

コード全体をいくつかのメソッドでラップできます。

using System;
using System.Collections.Generic;

public class FloydWarshallPathFinder {
    private int N;
    private int[,] D;
    private int[,] R;

    public FloydWarshallPathFinder(int NumberOfVertices, int[,] EdgesLengths) {
        N = NumberOfVertices;
        D = EdgesLengths;
        R = null;
    }

    public int[,] FindAllPaths() {
        R = new int[N, N];

        for (int i = 0; i < N; i++)
        {
            for (int t = 0; t < N; t++)
            {
                R[i, t] = t;
            }
        }

        for (int k = 0; k < N; k++)
        {
            for (int v = 0; v < N; v++)
            {
                for (int u = 0; u < N; u++)
                {
                    if (D[u, k] + D[k, v] < D[u, v])
                    {
                        D[u, v] = D[u, k] + D[k, v];
                        R[u, v] = R[u, k];
                    }
                }
            }
        }

        return R;
    }

    public List<Int32> FindShortestPath(int start, int end) {
        if (R == null) {
            FindAllPaths();
        }

        List<Int32> Path = new List<Int32>();

        while (start != end)
        {
            Path.Add(start);

            start = R[start, end];
        }

        Path.Add(end);

        return Path;
    }
}

public class MainClass
{
    public static void Main()
    {
        int N = 4;
        int[,] D = new int[N, N];

        for (int i = 0; i < N; i++) {
            for (int t = 0; t < N; t++) {
                if (i == t) {
                    D[i, t] = 0;
                } else {
                    D[i, t] = 9999;
                }
            }
        }

        D[0, 2] = 1;
        D[1, 0] = 7;
        D[1, 2] = 6;
        D[2, 3] = 5;
        D[3, 1] = 2;

        FloydWarshallPathFinder pathFinder = new FloydWarshallPathFinder(N, D);

        int start = 0;
        int end = 1;

        Console.WriteLine("Path: {0}", String.Join(" -> ", pathFinder.FindShortestPath(start, end).ToArray()));
    }
}

ウィキペディアでこのアルゴリズムを読んで、ここで自動的に生成されたいくつかのデータ構造を取得できます

于 2010-12-24T13:41:03.460 に答える
5

Floyd アルゴリズムを使用している場合、グラフのノード i からノード j までの最短距離のみが保存されます。そのため、ノードへのパスを保存することもできます。どうやってするの？

それを実装する方法の1つは、親（パス内の現在のノードの前のノードであるノード）ノードを保存することです。パスを含む別のマトリックスを作成する必要があります。次のようになります。

int[,] pathS = new int[matrixDimention, matrixDimention];
for (int i = 0; i < splitValues.Length; i++){
    intValues[i / (matrixDimention), i % (matrixDimention)] = Convert.ToInt32(splitValues[i]);
    pathS[i / (matrixDimention), i % (matrixDimention)] = -1;    
}
.....
for (int k = 1; k < n+1; k++)
    for (int i = 1; i < n+1; i++)
        for (int j = 1; j < n+1; j++)
            if (intValues[i, j] > intValues[i, k] + intValues[k, j]){                
                intValues[i, j] = intValues[i, k] + intValues[k, j];
                pathS[i,j] = k;
                string str_intvalues = intValues[i, j].ToString();
                MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
            }
            else{                
                string str_intvalues = intValues[i, j].ToString();
                MessageBox.Show("Shortest Path from i to j is: " + str_intvalues);
            }

これで、ノード i と j の間の中間パスを含む追加の pathS 配列ができました。理解を深めるために、pathS[i,j] はこの 2 つのノードの間のノードであることを考慮する必要があります (例: i -> [k] -> j)。しかし、パスは 3 ノードよりも長くなる可能性があります (そのため、[] 中かっこでノード k を書きました)。したがって、i と k の間のパス - pathS[i,k] と k と j の間のパス - pathS[k,j] をチェックする必要があります。そして、いくつかの i と j の間の pathS が「-1」に等しくなるまで、同じことを再帰的に行います。

于 2010-12-24T13:41:23.333 に答える