pygraphs.bfs_shortest_path#

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

Compute the shortest path 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:

A list of vertex indices representing the shortest path from the starting vertex to the ending vertex in the graph. If there is no path from the starting vertex to the ending vertex, an empty list is returned.

Return type:

List[int]

See also

pygraphs.bfs()

Core implementation of BFS.

Examples

Create a simple disconnected graph of 7 vertices and compute the shortest path 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).#

1from pygraphs import bfs_shortest_path, 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_path = bfs_shortest_path(graph, start_vertex, end_vertex)
9print(shortest_path)

[0, 2, 3, 4]

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

1from pygraphs import bfs_shortest_path, 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_path = bfs_shortest_path(graph, start_vertex, end_vertex)
9print(shortest_path)

[2, 1, 0]