0

Given an directed unweighted acylic graph, I am trying to adapt Floyd-Warshall algorithm to count the number of paths between 2 vertices. My code currently looks like this:

for all k in 1 to n for all i in 1 to n for all j in 1 to n Aij = Aij + ( Aik * Akij).

Therefore, instead of checking and replacing for min distance, I am doing the following:

Count of paths between (i,j) without k + ( Count of paths from i to k * Count of paths from k * j )

My final array, should have the number of paths between any 2 vertices.

I am not able to prove that this does not give me the count of simple paths between 2 vertices, but there are no suggestions to use this approach elsewhere.

Can someone provide a counter example where this fails?

PS: This is not my homework, but just a programming exercise I picked up.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
grdvnl
  • 636
  • 6
  • 9
  • `I am not able to prove that this does not give me the count of simple paths between 2 vertices` that means nothing - in order to know for sure if it is correct or not - you should either prove it is working, or find a counter example that shows it doesn't. – amit Apr 19 '12 at 18:17

2 Answers2

5

In an undirected unweighted acylic graph there's at most 1 path between any two vertices. If there were more distinct paths, they would create a cycle. (not relevant after question was edited)

For directed graphs, I don't see a problem with your algorithm. The usage of modified Floyd-Warshall algorithm is actually mentioned in this paper. The reason it's not used widely is probably its complexity - O(n3) compared to O(m+n) of this simple approach

Community
  • 1
  • 1
voidengine
  • 2,504
  • 1
  • 17
  • 29
  • I apologize for the typo. I was referring to a directed graph. Corrected the mistake in the original post. – grdvnl Apr 19 '12 at 16:41
  • Great, the paper explains what I needed. I also assumed I could discard the results in the diagonal elements end up being non-zero, as stated in the paper. – grdvnl Apr 19 '12 at 18:48
2

In the cyclic graph case, you can't do this with the straight Floyd-Warshall algorithm, because counting simple paths requires you to keep track of where you've been. Dynamic programming assumes that the state being computed is only a function of the states in the recurrence, which is not true in this case.

However, I don't see why this wouldn't work. But why use Floyd-Warshall to compute just two verticies (just use a DFS or BFS).

dfb
  • 13,133
  • 2
  • 31
  • 52
  • Yes, I could use DFS/BFS. But, wanted to check the correctness of using Floyd-Warshall. Also, in case of cycles, at the end of computation, I could discard the result if any one of diagonal elements could ending up being a non-zero value. Again, I understand this is not the most efficient. – grdvnl Apr 19 '12 at 18:40