floyd warshall 上的并行 linq

Question

我们遇到了这个图形问题，我们需要实施 Floyd Warshall，所以我们做到了。虽然我们有点不喜欢这个算法，因为它很慢。

我们想知道是否可以在第二个循环中应用并行 linq，这样我们可以稍微加快算法速度

Question: Speed up the For loop with var i

private int[,] FloydWarshall(int[,] matrix)
   {
     var loopCount = matrix.GetLength(0);
     var next = CreatePredecessorMatrix(matrix);

        for (var k = 0; k < loopCount; k++)
        {
            for (var i = 0; i < loopCount; i++)
            {
                for (var j = 0; j < loopCount; j++)
                {
                    if (matrix[i, j] > matrix[i, k] + matrix[k, j])
                    {
                        matrix[i, j] = matrix[i, k] + matrix[k, j];
                        next[i, j] = next[k, j];
                    }
                }
            }
        }
        return next;
   }

Answer 1

是否用 Parallel.For 代替 "var i" for-loop 不能达到与并行 Linq 相同的加速？

Answer 2

Viider Storm 关于 Parallel For 的非常好的建议

   private int[,] FloydWarshall(int[,] matrix)
    {
        var loopCount = matrix.GetLength(0);
        var next = CreatePredecessorMatrix(matrix);
        for (var k = 0; k < loopCount; k++)
        {
            Console.WriteLine(k);

            Parallel.For(0, loopCount, i =>
            {
                for (var j = 0; j < loopCount; j++)
                {
                    if (matrix[i, j] > matrix[i, k] + matrix[k, j])
                    {
                        matrix[i, j] = matrix[i, k] + matrix[k, j];
                        next[i, j] = next[k, j];
                    }
                }
            });
        }
        return next;
    }

感谢您的输入！

floyd warshall 上的并行 linq

Parallel linq on floyd warshall

c#

algorithm

linq

graph

floyd-warshall