pygraphs.bfs_shortest_distance#

bfs_shortest_distance(graph, start, end, *, max_distance=None, _skip_check=False)[source]#

Compute the shortest distance from a starting vertex to an ending vertex.

Parameters:

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

  • start (Integral) – The starting vertex index for the BFS.

  • end (Integral) – The ending vertex index for the BFS.

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

  • _skip_check (bool)

Returns:

The distance from starting vertex to ending vertex. Or -1 if not reachable.

Return type:

int

See also

pygraphs.bfs()

Core implementation of BFS.

pygraphs.bfs_distances()

Perform a breadth-first search (BFS) 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 distance from a starting vertex (0) to an other vertex.

../../_images/graph.png

Disconnected graph with 7 vertices for BFS example. Shortest path from vertex 0 to vertex 4 is (0 -> 2 -> 3 -> 4) with distance 3.#

1from pygraphs import bfs_shortest_distance, Graph
2
3graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]]
4graph = Graph.from_adjacency(graph)
5start_vertex = 0
6end_vertex = 4
7
8shortest_dist = bfs_shortest_distance(graph, start_vertex, end_vertex)
9print(shortest_dist)

3

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

../../_images/graph_directed.png

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

1from pygraphs import bfs_shortest_distance, Graph
2
3graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []]
4graph = Graph.from_adjacency(graph)
5start_vertex = 2
6end_vertex = 0
7
8shortest_dist = bfs_shortest_distance(graph, start_vertex, end_vertex)
9print(shortest_dist)

2