C/C++ 执行邻接 2 距离矩阵的最佳算法 [由 Floyd-Warshall 解决]

Question

INITIAL ISSUE

大家好

我已经找到了几种算法来完成这项任务。但所有这些代码都考虑了每个节点或边缘的权重值。

我的目标比这更容易，它是从邻接一个得到距离矩阵。

输入将是:

  a b c d e f    connected vertices to i
a 0 1 0 0 0 0    1
b 1 0 1 1 0 0    3
c 0 1 0 0 0 0    1
d 0 1 0 0 1 0    2
e 0 0 0 1 0 1    2
f 0 0 0 0 1 0    1
                ---
            Sum: 10  -> Edges = Sum/2 = 5

输出将是:

  a b c d e f
a 0 1 2 2 3 4
b 1 0 1 1 2 3
c 2 1 0 2 3 4
d 2 1 2 0 1 2
e 3 2 3 1 0 1
f 4 3 4 2 1 0

提前感谢您的任何建议，

大卫·亚历杭德罗。

SOLUTION FOUND

C 中的 Floyd-Warshall 内核

for (k = 0; k < n; ++k) 
{
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < n; ++j)
        {
            if ((dist[i][k] * dist[k][j] != 0) && (i != j))
            {
                if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0))
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }                   
}

Answer 1

如果您已经找到仅使用权重关联的算法，请使用它们，但将每个权重设置为 1。

BFS无论如何这都是我的建议。