5

Is it possible to convert an adjacency matrix of ones and zeros as defined here into a distance matrix as defined here where each link would be of unit length 1?

smci
  • 32,567
  • 20
  • 113
  • 146
pyCthon
  • 11,746
  • 20
  • 73
  • 135

1 Answers1

4

An adjacency matrix of ones and zeros is simply a representation of an undirected graph. To get the distances between any two vertices of an unweighted graph, you can use breadth first search.

Assuming you have an n by n matrix:

for each vertex i:
    initialize an nxn matrix M
    run breadth-first search starting at i
    copy distances into row i of M
    return M
tskuzzy
  • 35,812
  • 14
  • 73
  • 140
  • 2
    Instead of breadth first search, it would probably be better to use an algorithm for the [all-pairs shortest-path problem](http://en.wikipedia.org/wiki/Shortest_path_problem) – Hans Apr 09 '12 at 21:29
  • this will take forever for a large case – pyCthon Apr 09 '12 at 22:16
  • 1
    @Hans: Floyd-Warshall takes `O(V^3)` time whereas BFS takes `O(V^2+VE)`. BFS is always faster, and significantly more so for sparse graphs. The fastest way of finding the shortest path in an undirected graph is always BFS. – tskuzzy Apr 10 '12 at 07:48
  • 1
    @tskuzzy: what's V and E? Number of nodes/edges? Here, distances between all pairs are needed, as far as I understand it BFS only finds the distance to the root node - can you elaborate on that? Also, in real life constants actually matter... – Hans Apr 10 '12 at 20:43
  • @Hans: Yes, V is the number of vertices and E is the number of edges. We run a BFS for each vertex, so that calculates the all-pairs shortest path. The constants associated with BFS are comparable to that of FW, if not smaller. If you benchmark the two, you would see BFS is superior. – tskuzzy Apr 10 '12 at 21:53
  • both good points i ended up having to use Dijkstra's algorithm with Fibonacci heaps from an implementation i found on the web – pyCthon Apr 15 '12 at 05:15