Thursday, April 19, 2012

Using Floyd-Warshall algorithm to count number of paths between 2 vertices

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.





No comments:

Post a Comment