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.

Pre-requisites :

1) Adjacency Matrix – The Adjacency Matrix of a graph G = (V,E), with is:

– if

– otherwise

2) Diameter – The Diameter of a Graph G = (V, E) is

Algorithm :

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.

QED

Pseudocode :

– length = 0

– count = 0

– A = adjacencyMatrix

– B = adjacencyMatrix

– while (length =< ): //

–

– = * //

– += 1

– =

return count

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