gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:52:40 24 4
gpt4 key购买 nike

基本上,使用 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
-------------------------------

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

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

最佳答案

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

关于c - 使用 Floyd-Warshall 算法确定一个 "odd"矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11900830/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com