我有一个表示图形的相邻矩阵。

我想执行弗洛伊德算法来计算每对顶点之间的最短路径。

而且我绝对可以以 O(N3) 的复杂性对它们进行迭代。

但是当 n = 10^3 时，R 将无法承受迭代。所以我正在寻找在矩阵运算中执行弗洛伊德算法的方法。

附加参考

理论上，我们可以参考MIT Isomap mat 文件。

但是我仍然对如何在 R 中执行“repmat”感到困惑，它会多次复制垫子。

I am new in MPI I have some arrays generated by processors. Each processor generated one array with DIFFERENT length. How can I merging all of them IN ORDER in to one array only stored in processor 0.

Eg:

Is there anyone can help me solve this problem. Thank for reading :)

我想使用Vectors 在 Haskell 中编写 Floyd-Warshall 所有对最短路径算法的有效实现，以期获得良好的性能。

实现非常简单，但不是使用 3 维 |V|×|V|×|V| 矩阵，使用二维向量，因为我们只读取前一个k值。

因此，该算法实际上只是传入 2D 向量并生成新的 2D 向量的一系列步骤。最终的 2D 向量包含所有节点 (i,j) 之间的最短路径。

我的直觉告诉我，确保在每一步之前评估先前的 2D 向量很重要，所以我在函数BangPatterns的prev参数fw和 strict上使用了foldl'：

但是，当使用 1000 个节点和 47978 条边的图运行这个程序时，事情看起来一点也不好看。内存使用率非常高，程序运行时间太长。该程序是用ghc -O2.

我重建了分析程序，并将迭代次数限制为 50：

然后我用+RTS -p -hcand运行程序+RTS -p -hd：

这……很有趣，但我想这表明它正在积累大量的 thunk。不好。

好的，所以在黑暗中拍摄了几张照片后，我添加了一个deepseqinfw以确保prev 真的被评估：

现在情况看起来好多了，我实际上可以在不断使用内存的情况下运行程序完成。很明显，prev论点的轰动是不够的。

为了与之前的图表进行比较，以下是添加 50 次迭代后的内存使用情况deepseq：

好的，事情好多了，但我还有一些问题：

1. 这是这个空间泄漏的正确解决方案吗？我觉得插入deepseqa 有点难看是错误的？
2. 我Vector在这里使用 s 是惯用的/正确的吗？我正在为每次迭代构建一个全新的向量，并希望垃圾收集器会删除旧Vector的 s。
3. 我还能做些什么来让这种方法运行得更快吗？

作为参考，这里是graph.txt：http ://sebsauvage.net/paste/?45147f7caf8c5f29#7tiCiPovPHWRm1XNvrSb/zNl3ujF3xB3yehrxhEdVWw=

这里是main：

我正在尝试为加权有向图实现 Floyd Warshall 图算法，但无法使其工作。

后继权重仅在 1 中，否则为 0。

实现看起来像这样（尽管我从某个地方获取了实现）。

我在为我试图弄清楚的自我项目实施 Floyd-Warshall 算法时遇到了困难。我有一组测试数据，但是当我在ShortestPath创建后打印出来时，我只得到一个null和一个内存地址。不确定从这里开始使用该算法的确切位置。非常感谢任何帮助！

我阅读了Wikipedia给出的方法，通过修改 Floyd Warshall 算法在图中以两个给定点打印短路径。我对此进行了编码，但它并没有真正给出预期的输出：

1. 将图中的所有元素初始化minimumDistanceMatrix[i][j]为各自的权重，将矩阵中的所有元素初始化shortestPathCalculatorMatrix [i][j]为-1。

2. 然后 ：

   /li>

3. 然后 ：

   /li>

PS：pathCityList是一个向量，在调用之前假定为空findShortestPathListBetween。在此调用结束时，此向量中包含所有中间节点。

有人可以指出我可能会出错的地方吗？

我刚开始学习图算法，更具体地说是 Floyd-Warshall 算法。在维基百科中查看修改后的算法以允许重建路径，我注意到它保留了中间节点，而不是更合乎逻辑（在我看来）的方式 - 保存下一跳。此外，在课本中，方式是由一个到最后一个节点保存的。为什么要以这种方式保存路径？

我指的是本教程：http ://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/

作者提到了这一点：

我们还可以通过将前驱信息存储在单独的二维矩阵中来修改解决方案以打印最短路径。

我对这个前身信息有点困惑。

那么，如何存储路径以供以后显示呢？

我见过有人说可以（轻松地）修改 Floyd-Warshall 以检测周期。注意：我假设图表没有负循环。我想知道如何修改算法？为什么它是正确的？另外，你可以让它检测到哪些周期？最短，最长，长度为 k？——你需要对算法进行哪些调整？

我读了这个问题，这让我开始思考这个问题： Find cycle of shortest length in adirected graph with positive weights

对于上面的链接，我不明白为什么要制作 adj 的对角线。matrix = INFINITY 为我们提供了通过 (i,i) 的最短长度的循环。

最后，这个网站：http ://en.algoritmy.net/article/45708/Floyd-Warshall-algorithm 说：

所以我认为我不明白这一点，因为这似乎是错误的，因为如果记忆对我有用，则无法在多时间内完成检测所有周期。我是否误解了所说的内容？（另外，不太确定前辈矩阵是什么意思。）

在接受该程序的输入时遇到问题。还有，不知道怎么填那些空白的功能textBox1_TextChanged，textBox9_TextChanged。Form1_Load.还有这些是什么；(object sender, EventArgs e)? 帮助将不胜感激！这是我在 c# 中经验最少的情况下能走多远。