c - 使用Floyd-Warshall算法确定 "odd"矩阵

Question

基本上，使用 Floyd-Warshall 算法的目的是确定连通图中两个节点之间的最短路径。我想做的不是简单地找到最短路径，而是想要权重均匀的最短路径。

例如，这是 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 
-------------------------------

我的代码当前所做的是获得最佳权重，该权重在每个单独的“奇数”和“偶数”矩阵中表示。

我缺乏理解的是，当最佳值位于相反矩阵(奇/偶)时，“奇”和“偶”矩阵如何得出非最佳值。在我看来，必须有某种循环或递归才能做到这一点，但我不知道如何实现这一点。

Answer 1

不是用 C 语言，但这应该不是问题。我相信 F-W 需要进行两次修改才能获得最短的奇数/偶数路径:

1. 它需要运行两次。这是因为如果路径自身循环，则可能会改变均匀度。如下图所示:A --5--> B --2-->(回到 A)。为了沿着均匀的路径从 A 到 B，我们需要走 A-B-A-B。但是，如果我们不能通过运行两次获得一定均匀度的路径，那么运行两次以上就没有意义了。

2. 您需要尝试所有组合才能找到更好的路径(请参阅从 0 到 1 的最内层循环)。通过添加奇数边缘等，迄今为止的偶数路径可能会成为新的最佳奇数路径。

我认为这个算法应该是正确的，如果你发现任何错误，请随时骂我。 >D

编辑:添加路径内存(用//ADDED 标记的部分)。当然，这使得算法内存效率低下，因此只有在确实需要时才应使用。 ATM 我想不出一种方法可以让标准 F-W 路径重建在这种情况下发挥作用。由于路径可能比顶点数量长，我不确定路径重建将如何工作。我还没有广泛测试路径内存，所以它可能会被窃听。不过可能工作正常。

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();
        }
    }
}