1 
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

Floyd-Warshall Kernell C 中

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];
                }
            }
        }
    }                   
}
4

2 回答 2

2

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

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

于 2012-06-12T21:40:12.060 回答
1

将邻接矩阵中的“无限”（即大于任何合理距离）值更改为零，然后在结果矩阵上运行Floyd-Warshall。

NominSim 建议的 BFS 需要从每个起始顶点运行，以获得所有顶点的距离。

于 2012-06-12T21:51:44.723 回答