Floyd module¶

This is Floyd’s algorithm for finding the shortest distance between any two pair of vertices in the graph, also known as the all-paths problem.

It works by using a weighted adjacency matrix such that

If \(u \rightarrow v\) than \(A[u, v] = \text{Wt}(uv)\)

If \(u \not\rightarrow v\) than \(A[u, v] = \infty\)

If \(u = v\) than \(A[u, v] = 0\)

It then attempts to route a path from every vertex through every other vertex to the destination vertex.

Algorithm 2.7.1 on page 41

Floyd.build_matrix(G)¶

Build the weighted adjacency matrix from the graph G.

If \(u \rightarrow v\) than \(A[u, v] = \text{Wt}(uv)\)

If \(u \not\rightarrow v\) than \(A[u, v] = \infty\)

If \(u = v\) than \(A[u, v] = 0\)

Parameters

Gnx.Graph

The graph that we need to build a weighted adjacency matrix for.

Returns

np.ndarray

The weighted adjacency matrix

Floyd.floyd(G)¶

Performs Floyd’s algorithm for the all-paths problem, returning a matrix such that M[v, u] is the shortest distance between u and v.

Parameters

Gnx.Graph

The graph we wish to solve the all-paths problem on

Returns

np.ndarray

An n by n matrix with the shortest distance between any two vertices encoded in it.