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.
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).
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