1 
INITIAL ISSUE

Good day everybody,

I've already found several algorithms to do this task. The but is that all those codes consider a weight value per node or edge.

My aim is easier than that, It is to get the distance matrix from adjacency one.

The input would be:

  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

The output would be:

  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

Thanks in advance for any suggestion,

David Alejandro.

SOLUTION FOUND

Floyd-Warshall Kernell in 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 に答える