C/C++ Best algorithm to perfom Adjacency2Distance matrix [Solved by Floyd-Warshall]

Question

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

Perhaps duplicate of http://stackoverflow.com/questions/10079876/converting-a-adjacency-matrix-to-a-distance-or-hop-matrix — ffao, Jun 12 '12 at 22:01
Theoretical best so far seems to be `O(n² log n)` (see http://www.waset.org/journals/ijcms/v3/v3-5-43.pdf), but I can't really understand it. — ffao, Jun 12 '12 at 22:16

score 2 · Accepted Answer · answered Jun 12 '12 at 21:40

2

If you've already found algorithms to do it only with weight associations, use them, but set every weight to 1.

BFS would be my suggestion in any case.

answered Jun 12 '12 at 21:40

NominSim

8,447
3
28
38

Good suggestion. For basic needs, best way is going deep! – Another.Chemist Jun 13 '12 at 19:44

score 1 · Answer 2 · answered Jun 12 '12 at 21:51

1

Change zeros for an "infinite" (i.e. larger than any reasonable distance) value in your adjacency matrix and then run Floyd-Warshall on the resulting matrix.

BFS as suggested by NominSim would need to be run from each starting vertex in order to get you distances for all vertices.

answered Jun 12 '12 at 21:51

Pablo

8,644
2
39
29

BFS n times -> O(mn + n²). Floyd-Warshall is far easier to code, though. – ffao Jun 12 '12 at 22:13
1

But O(mn) with an adjacency matrix is O(n^3) so they're both O(n^3). In any case, I wasn't comparing efficiency, I was just stating that plain BFS only solves single-source shortest paths, whereas the OP asks for all-pairs. – Pablo Jun 12 '12 at 22:17

C/C++ Best algorithm to perfom Adjacency2Distance matrix [Solved by Floyd-Warshall]

2 Answers2