- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
基本上,使用 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 需要两次修改才能获得最短的奇数/偶数路径:
它需要运行两次。这是因为如果一条路径在其自身上循环,它可能会改变均匀度。就像在这个图中:A --5--> B --2-->(回到 A)。为了在平坦的路径上从 A 到 B,我们需要走 A-B-A-B。但是,如果我们不能得到一条运行两次的特定均匀度的路径,那么运行超过两次就没有意义了。
您需要尝试所有组合以找到更好的路径(请参阅从 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/
#include using namespace std; class C{ private: int value; public: C(){ value = 0;
这个问题已经有答案了: What is the difference between char a[] = ?string?; and char *p = ?string?;? (8 个回答) 已关闭
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 7 年前。 此帖子已于 8 个月
除了调试之外,是否有任何针对 c、c++ 或 c# 的测试工具,其工作原理类似于将独立函数复制粘贴到某个文本框,然后在其他文本框中输入参数? 最佳答案 也许您会考虑单元测试。我推荐你谷歌测试和谷歌模拟
我想在第二台显示器中移动一个窗口 (HWND)。问题是我尝试了很多方法,例如将分辨率加倍或输入负值,但它永远无法将窗口放在我的第二台显示器上。 关于如何在 C/C++/c# 中执行此操作的任何线索 最
我正在寻找 C/C++/C## 中不同类型 DES 的现有实现。我的运行平台是Windows XP/Vista/7。 我正在尝试编写一个 C# 程序,它将使用 DES 算法进行加密和解密。我需要一些实
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
有没有办法强制将另一个 窗口置于顶部? 不是应用程序的窗口,而是另一个已经在系统上运行的窗口。 (Windows, C/C++/C#) 最佳答案 SetWindowPos(that_window_ha
假设您可以在 C/C++ 或 Csharp 之间做出选择,并且您打算在 Windows 和 Linux 服务器上运行同一服务器的多个实例,那么构建套接字服务器应用程序的最明智选择是什么? 最佳答案 如
你们能告诉我它们之间的区别吗? 顺便问一下,有什么叫C++库或C库的吗? 最佳答案 C++ 标准库 和 C 标准库 是 C++ 和 C 标准定义的库,提供给 C++ 和 C 程序使用。那是那些词的共同
下面的测试代码,我将输出信息放在注释中。我使用的是 gcc 4.8.5 和 Centos 7.2。 #include #include class C { public:
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
我的客户将使用名为 annoucement 的结构/类与客户通信。我想我会用 C++ 编写服务器。会有很多不同的类继承annoucement。我的问题是通过网络将这些类发送给客户端 我想也许我应该使用
我在 C# 中有以下函数: public Matrix ConcatDescriptors(IList> descriptors) { int cols = descriptors[0].Co
我有一个项目要编写一个函数来对某些数据执行某些操作。我可以用 C/C++ 编写代码,但我不想与雇主共享该函数的代码。相反,我只想让他有权在他自己的代码中调用该函数。是否可以?我想到了这两种方法 - 在
我使用的是编写糟糕的第 3 方 (C/C++) Api。我从托管代码(C++/CLI)中使用它。有时会出现“访问冲突错误”。这使整个应用程序崩溃。我知道我无法处理这些错误[如果指针访问非法内存位置等,
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 7 年前。
已关闭。此问题不符合Stack Overflow guidelines 。目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的,因为
我有一些 C 代码,将使用 P/Invoke 从 C# 调用。我正在尝试为这个 C 函数定义一个 C# 等效项。 SomeData* DoSomething(); struct SomeData {
这个问题已经有答案了: Why are these constructs using pre and post-increment undefined behavior? (14 个回答) 已关闭 6
我是一名优秀的程序员,十分优秀!