This Algorithm will build on a new understanding of a way to look at Graphs. In particular, we will use the Adjacency Matrix and the Diameter of a Graph to build this Algorithm. The Computational Complexity of this Algorithm will be discussed once the pseudocode is presented.
1) Adjacency Matrix – The Adjacency Matrix of a graph G = (V,E), with is:
2) Diameter – The Diameter of a Graph G = (V, E) is
The Algorithm is based off of 2 ideas:
1) The length of any path between any two vertices is less than the Diameter of a Graph.
2) In any Graph G = (V,E) , we have that , has of length ‘k’.
Proof of 2):
We will use Induction.
a) For k = 1, by definition, the Adjacency Matrix tells us whether or not an edge exists between two vertices. In a Graph, and Edge is the only path of length-1.
b) Inductive Hypothesis : Assume that, for some , gives the number of all possible paths from a vertex to another vertex of length ‘k’.
c) For , we have that : = .
Now, by the Inductive Hypothesis, ,
Now, for any vertex, all paths that end at a vertex must come in from one of it’s adjacent vertices. By definition of the Adjacency Matrix and Matrix Multiplication, then:
By definition, for all adjacent vertices to , = 1,
Therefore, the paths from a vertex to a vertex of length (k + 1), are the sum of the paths of length (k), from vertex to all the adjacent vertices of .
Therefore, 2) is true.
– length = 0
– count = 0
– A = adjacencyMatrix
– B = adjacencyMatrix
– while (length =< ): //
– = * //
– += 1
Now, we know that and therefore, all paths of all possible lengths between and are summed up and return under the variable ‘count’.
Computational Complexity : . Now, is between ‘1’ and ‘n’. Therefore, we will have that the computational complexity of our Algorithm will be bounded by : .
The comes from the Matrix Multiplication Algorithm, which can be reduced by using a Cache, or by distributing the task. However, for most purposes, the Algorithm is cubic in time.
Space Complexity : . Here, the Squared Space Complexity arises because of the need to store the Adjacency Matrix in-memory.
The proof of correctness for this Algorithm follows directly from 2).