All pairs all paths on a graph?

The Floyd-Warshall generalization that gets a rough approximation of paths is this: procedure FloydWarshall () for k := 1 to n for I := 1 to n for j := 1 to n pathij = pathij + pathik*pathkj Here is a very rough idea on how to scale this. Disclaimer - This isn't concrete -it's very hand wavy, but hopefully it helps more than confuses. It helps to understand how the algorithm works.It starts on an adjacency matrix of the graph.

In each iteration k, we're saying the number of paths from I to j is equal to the number of paths in prior iterations from I to j plus the number of paths from I to j via k Thus Break the graph in to n arbitrary sub-adjacency matricies of size k x k, compute above on each of them. Now you have the number of paths and start combining submatricies by recomputing part of the above on the combined matrix.I. E, we only need to recompute n/2 values for k when recombining.

I found this, which looks like a similar direction theory.stanford.edu/~oldham/publications....

The Floyd-Warshall generalization that gets a rough approximation of paths is this: procedure FloydWarshall () for k := 1 to n for I := 1 to n for j := 1 to n pathij = pathij + pathik*pathkj Here is a very rough idea on how to scale this. Disclaimer - This isn't concrete -it's very hand wavy, but hopefully it helps more than confuses. It helps to understand how the algorithm works.It starts on an adjacency matrix of the graph.

In each iteration k, we're saying the number of paths from I to j is equal to the number of paths in prior iterations from I to j plus the number of paths from I to j via k. Thus Break the graph in to n arbitrary sub-adjacency matricies of size k x k, compute above on each of them. Now you have the number of paths and start combining submatricies by recomputing part of the above on the combined matrix.

I. E, we only need to recompute n/2 values for k when recombining. I found this, which looks like a similar direction theory.stanford.edu/~oldham/publications....

Thanks for the input. – sc_ray Mar 11 at 15:01.

In such a graph with V vertices, you have about V^2 different pairs. Let's imagine a worst case scenario where you have a full graph (one where edges exist between every pair). Paths can have anywhere between 1 edge and V-1 edges, because you do not allow duplicate vertices in a path.

Between each pair of vertices: There is only one path with 1 edge; There are V-2 paths with 2 edges: using any intermediate vertex that isn't the origin or destination; There are (V-2)(V-3) paths with 3 edges: using any two distinct intermediate vertices; There are (V-2)(V-3)(V-4) paths with 4 edges; There are prod{k=1 -> n-1}(V-k-1) paths with n edges. Given that, we know that there are at most V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(V-k-1)) total paths for a graph with V vertices. The total number of paths is therefore P(V) = V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(V-k-1)) = V^2*sum{i=1 -> V-1}(O(V^V)) = O(V^3*V^V) = O(V!

). Now imagine an ideal world where you can compute each path in constant time. Your algorithm would take O(1*V!

) = O(V! ) time to run, which is impratical. There might be an algorithm that can count the paths without enumerating them, and thus get a more efficient algorithm.

– R. Martinho Fernandes Mar 9 at 18:31 Thanks for the analysis. I assumed it will be some obscene runtime like O(V!

). I am looking for practical strategies to tackle problems of this magnitude. – sc_ray Mar 9 at 20:58 straight html should work: & Sigma; and & Pi; (no blank after the & sign).

See also List_of_XML_and_HTML_character_entity_references – Denis Apr 11 at 15:46.

This SO page describes a DFS method for printing all non-cyclic paths between any two vertices--it also includes java code. You can modify it to find all such paths for all pairs of of vertices, but it's not the most efficient way of counting all paths between all vertices.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.