pygraphs.dijkstra_matrix

dijkstra_matrix(graph, *, weight_key='weight', max_distance=None, _skip_check=False)

Compute the shortest path distance matrix for all pairs of vertices.

Parameters:

• graph (Graph) – An instance of the Graph class representing the graph to be traversed.

• max_distance (Optional[Integral], optional (default: None)) – The maximum distance to search for in the Dijkstra. All vertices that are not reachable within this distance will be ignored.

• weight_key (str (default: 'weight')) – The key-name of the weight to use in the graph dictionnary structure. If an edge does not have weight, default weight is 1.0.

• _skip_check (bool)

Returns:

A 2D list representing the shortest path distance matrix, where the element at position (i, j) represents the shortest path distance from vertex i to vertex j. If a vertex is not reachable within the specified maximum distance, the distance will be -1.0.

Return type:

List[List[float]]

Notes

The function uses a Dijkstra approach to compute the shortest path distances, which is efficient for unweighted graphs. The time complexity is \(O(V(V + E))\), where \(V\) is the number of vertices and \(E\) is the number of edges in the graph. For a undirected graph, the distance matrix is symmetric, meaning that the distance from vertex \(A\) to vertex \(B\) is the same as the distance from vertex \(B\) to vertex \(A\) (i.e., \(\text{dist}(A, B) = \text{dist}(B, A)\)), since the edges can be traversed in both directions. For a directed graph, the distance matrix is not necessarily symmetric, since the edges can only be traversed in one direction (i.e., \(\text{dist}(A, B)\) may not be equal to \(\text{dist}(B, A)\)).

See also

pygraphs.dijkstra()

Core implementation of Dijkstra.

pygraphs.dijkstra_distances()

Perform a breadth-first search (Dijkstra) to compute the shortest path distances from a starting vertex to all other vertices in the graph, where the distance is defined as the number of edges in the shortest path between the vertices.

Examples

Create a simple disconnected graph of 7 vertices and compute the shortest path distance matrix for all pairs of vertices in the graph.

Disconnected and weighted graph with 7 vertices for Dijkstra example. Distance from vertex 0 to vertex 4 is 4.8 (0 -> 2 -> 3 -> 4). Thus dist[0, 4] = 4.8 and dist[4, 0] = 4.8 for this undirected graph.

from pygraphs import dijkstra_k_disk, Graph

graph = [
    [(1, 1.2), (2, 0.2)],
    [(0, 1.2), (2, 1.5)],
    [(0, 0.2), (1, 1.5), (3, 3.2)],
    [(2, 3.2), (4, 1.4)],
    [(3, 1.4)],
    [(6, 2.3)],
    [(5, 2.3)]
]
graph = Graph.from_adjacency(graph)

adjacency_matrix = bfs_matrix(graph)
print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):")
print(adjacency_matrix)

adjacency_matrix (shape=(7x7)):
[[ 0.0  1.2  0.2  3.4  4.8 -1.0 -1.0]
 [ 1.2  0.0  1.4  4.6  6.0 -1.0 -1.0]
 [ 0.2  1.4  0.0  3.2  4.6 -1.0 -1.0]
 [ 3.4  4.6  3.2  0.0  1.4 -1.0 -1.0]
 [ 4.8  6.0  4.6  1.4  0.0 -1.0 -1.0]
 [-1.0 -1.0 -1.0 -1.0 -1.0  0.0  2.3]
 [-1.0 -1.0 -1.0 -1.0 -1.0  2.3  0.0]]

This method can be applied for directed graphs as well, where the adjacency list represents the outgoing neighbors of each vertex.

Directed graph with 7 vertices for Dijkstra example. Shortest path from vertex 2 to vertex 0 is (2 -> 1 -> 0) with distance 2.7.

from pygraphs import dijkstra_k_disk, Graph

graph = [
    [(1, 1.2), (2, 0.2)],
    [(0, 1.2), (2, 1.5)],
    [(1, 1.5), (3, 3.2)],
    [(2, 1.4), (4, 1.4)],
    [(3, 1.4)],
    [(6, 2.3)],
    []
]
graph = Graph.from_adjacency(graph)

adjacency_matrix = bfs_matrix(graph)
print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):")
print(adjacency_matrix)

adjacency_matrix (shape=(7x7)):
[[ 0.0  1.2  0.2  3.4  4.8 -1.0 -1.0]
 [ 1.2  0.0  1.4  4.6  6.0 -1.0 -1.0]
 [ 0.2  1.4  0.0  3.2  4.6 -1.0 -1.0]
 [ 1.6  2.8  1.4  0.0  1.4 -1.0 -1.0]
 [ 3.0  4.2  2.8  1.4  0.0 -1.0 -1.0]
 [-1.0 -1.0 -1.0 -1.0 -1.0  0.0  2.3]
 [-1.0 -1.0 -1.0 -1.0 -1.0 -1.0  0.0]]