2

基本的に、Floyd-Warshall アルゴリズムを使用するポイントは、接続されたグラフ内の 2 つのノード間の最短経路を決定することです。私がやろうとしているのは、単に最短経路を見つけるのではなく、均等な重みでもある最短経路が欲しいということです。

たとえば、これは Floyd-Warshall アルゴリズムの単純な実装です。

#include <stdio.h>

main()
{
   int dist[10][10],succ[10][10],n,i,j,k;
    int newDist;

    scanf("%d",&n);
    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
        {
            dist[i][j]=999;
            succ[i][j]=j;
        }

    while (1)
    {
        scanf("%d %d %d",&i,&j,&k);

        if (i==(-1))
            break;

        dist[i][j]=k;
        distOdd[i][j]=k;
        distEven[i][j]=k;
    }

    printf("    ");

    for (i=0;i<n;i++)
        printf("%3d   ",i);

    printf("\n");

    for (i=0;i<n;i++)
    {
        printf("%3d ",i);

        for (k=0;k<n;k++)
            printf("%3d %d ",dist[i][k],succ[i][k]);

        printf("\n");
    }

    printf("-------------------------------\n");

    /* Floyd-Warshall */
    for (j=0;j<n;j++)
    {
        for (i=0;i<n;i++)
            if (dist[i][j]<999)
                for (k=0;k<n;k++)
                {
                    newDist=dist[i][j]+dist[j][k];
                    if (newDist<dist[i][k])
                    {
                        dist[i][k]=newDist;
                        succ[i][k]=succ[i][j];
                    }
                }

        printf("    ");

        for (i=0;i<n;i++)
            printf("%3d   ",i);
        printf("\n");

        for (i=0;i<n;i++)
        {
            printf("%3d ",i);

            for (k=0;k<n;k++)
                printf("%3d %d ",dist[i][k],succ[i][k]);

            printf("\n");
        }

        printf("-------------------------------\n");
    }

    for (i=0;i<n;i++)
        for (j=0;j<n;j++)
            if (dist[i][j]==999)
                printf("No path from %d to %d\n",i,j);
            else
            {
                printf("Distance %d for %d ",dist[i][j],i);
                for (k=succ[i][j];
                    k!=j;
                    k=succ[k][j])
                        printf("%d ",k);

                printf("%d\n",j);
            }
}

次の入力があるとします。

6
0 1 1
1 2 1
2 3 1
3 1 1
1 4 1
4 5 1
-1 -1 -1

次の出力が必要です（フォーマットは無視してください。各ステップで「奇数行列」を見つける方法が必要です）

initial odd matrix
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 0
odd matrix
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 1
odd matrix
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 2
odd matrix
999 0   1 1 999 2   3 1 999 4 999 5 
999 0 999 1   1 2 999 3   1 4 999 5 
999 0 999 1 999 2   1 3 999 4 999 5 
999 0   1 1 999 2   3 1 999 4 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2   2 2 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1   2 1 999 3   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 3
odd matrix
999 0   1 1   5 1   3 1   5 1 999 5 
999 0   3 2   1 2   5 2   1 4 999 5 
999 0   5 3   3 3   1 3   3 3 999 5 
999 0   1 1   5 1   3 1   5 1 999 5 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0   4 1   2 1   6 1   2 1 999 5 
999 0   6 2   4 2   2 2   4 2 999 5 
999 0   2 3   6 3   4 3   6 3 999 5 
999 0   4 1   2 1   6 1   2 1 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 4
odd matrix
999 0   1 1   5 1   3 1   5 1   3 1 
999 0   3 2   1 2   5 2   1 4   5 2 
999 0   5 3   3 3   1 3   3 3   7 3 
999 0   1 1   5 1   3 1   5 1   3 1 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0   4 1   2 1   6 1   2 1   6 1 
999 0   6 2   4 2   2 2   4 2   2 4 
999 0   2 3   6 3   4 3   6 3   4 3 
999 0   4 1   2 1   6 1   2 1   6 1 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------
Process column 5
odd matrix
999 0   1 1   5 1   3 1   5 1   3 1 
999 0   3 2   1 2   5 2   1 4   5 2 
999 0   5 3   3 3   1 3   3 3   7 3 
999 0   1 1   5 1   3 1   5 1   3 1 
999 0 999 1 999 2 999 3 999 4   1 5 
999 0 999 1 999 2 999 3 999 4 999 5 
even matrix
999 0   4 1   2 1   6 1   2 1   6 1 
999 0   6 2   4 2   2 2   4 2   2 4 
999 0   2 3   6 3   4 3   6 3   4 3 
999 0   4 1   2 1   6 1   2 1   6 1 
999 0 999 1 999 2 999 3 999 4 999 5 
999 0 999 1 999 2 999 3 999 4 999 5 
-------------------------------

私のコードが現在行っていることは、個別の「奇数」と「偶数」の各マトリックスで表される最適な重みを取得することです。

私の理解不足は、最適値が反対の行列 (奇数/偶数) にある場合に、「奇数」行列と「偶数」行列がどのように非最適値になるかということです。それを行うには、ある種のループまたは再帰が必要になるように思えますが、これをどのように達成するかについてはわかりません。

4

1 に答える 1

2

Cではありませんが、それは問題にはなりません。最短の奇数/偶数パスを取得するには、FW に 2 つの変更が必要だと思います。

  1. 2 回実行する必要があります。これは、パスがそれ自体でループすると、偶数性が切り替わる可能性があるためです。このグラフのように: A --5--> B --2--> (A に戻る)。偶数経路で A から B に到達するには、ABAB に移動する必要があります。ただし、2 回実行してもある程度均一なパスが得られない場合は、2 回以上実行しても意味がありません。

  2. より良いパスを見つけるには、すべての組み合わせを試す必要があります (0 から 1 になる最も内側のループを参照してください)。これまでの偶数パスは、奇数エッジを追加するなどして、新しい最適な奇数パスになる場合があります。

このアルゴリズムは正しいはずだと思います。間違いを見つけたら、遠慮なく私に怒鳴ってください。>D

編集：追加されたパスの記憶（// ADDEDでマークされた部分）。もちろん、これによりアルゴリズムのメモリが非効率になるため、本当に必要な場合にのみ使用する必要があります。ATM この場合、標準の FW パス再構築を機能させる方法が思い浮かびません。パスは頂点の数よりも長くなる可能性があるため、パスの再構築がどのように機能するかはわかりません。パスの記憶を広範囲にテストしていないため、バグがある可能性があります。おそらく正常に動作します。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 5;

            // Generate graph
            Random r = new Random(1);
            // ADDED
            List<int>[,,] path = new List<int>[n, n, 2];
            int[,,] cost = new int[n, n, 2];
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    // ADDED
                    path[i, j, 0] = new List<int>{i};
                    path[i, j, 1] = new List<int>{i};

                    if (i == j)
                    {
                        cost[i, j, 0] = 0;
                        cost[i, j, 1] = -1;
                        continue;
                    }
                    int x = r.Next() % 9 + 1;

                    if (r.Next(100) < 60)
                    {
                        cost[i, j, 0] = -1;
                        cost[i, j, 1] = -1;
                        continue;
                    }

                    cost[i, j, x % 2] = x;
                    cost[i, j, 1 - (x % 2)] = -1;
                }
            }

            // Print edge weights
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (cost[i, j, 0] != -1)
                        Console.Write(cost[i, j, 0] + "\t");
                    else
                        Console.Write(cost[i, j, 1] + "\t");
                }
                Console.WriteLine(" ");
            }
            Console.ReadLine();

            // Find shortest odd and even paths
            for (int s = 0; s < 2; s++)
            {
                for (int k = 0; k < n; k++)
                    for (int i = 0; i < n; i++)
                        for (int j = 0; j < n; j++)
                            for (int u = 0; u <= 1; u++)
                                for (int v = 0; v <= 1; v++)
                                {
                                    if (cost[i, k, u] == -1 || cost[k, j, v] == -1)
                                        continue;
                                    int newCost = cost[i, k, u] + cost[k, j, v];
                                    if (newCost < cost[i, j, newCost % 2] || cost[i, j, newCost % 2] == -1)
                                    {
                                        cost[i, j, newCost % 2] = newCost;
                                        // ADDED
                                        path[i, j, newCost % 2] = path[i, k, u].Concat(path[k, j, v]).ToList();
                                    }
                                }
            }

            // Print results
            Console.WriteLine("\nShortest even paths: ");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(cost[i, j, 0] + "\t");
                Console.WriteLine(" ");
            }

            Console.WriteLine("\nShortest odd paths:");
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(cost[i, j, 1] + "\t");
                Console.WriteLine(" ");
            }

            Console.WriteLine();

            // ADDED
            // Example, print shortest odd path between vertices 3 and 1
            // This does not print the final q vertex
            int p = 3;
            int q = 1;
            foreach (int index in path[p, q, 1])
                Console.Write(index);

            Console.ReadLine();
        }
    }
}
于 2012-08-10T13:07:03.380 に答える