pygraphs.dijkstra_shortest_path#

dijkstra_shortest_path(graph, start, end, *, weight_key='weight', 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 Dijkstra.

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

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

  • max_distance (Optional[Real], optional (default: None)) – The maximum distance to search for in the Dijkstra. 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.dijkstra()

Core implementation of Dijkstra.

Examples

Create a simple disconnected graph of 7 vertices and compute the shortest path from a starting vertex (0) to an other vertex.

../../_images/weighted_graph.png

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

 1from pygraphs import dijkstra_k_disk, Graph
 2
 3graph = [
 4    [(1, 1.2), (2, 0.2)],
 5    [(0, 1.2), (2, 1.5)],
 6    [(0, 0.2), (1, 1.5), (3, 3.2)],
 7    [(2, 3.2), (4, 1.4)],
 8    [(3, 1.4)],
 9    [(6, 2.3)],
10    [(5, 2.3)]
11]
12graph = Graph.from_adjacency(graph)
13start_vertex = 0
14end_vertex = 4
15
16shortest_path = dijkstra_shortest_path(graph, start_vertex, end_vertex)
17print(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/weighted_graph_directed.png

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

 1from pygraphs import dijkstra_k_disk, Graph
 2
 3graph = [
 4    [(1, 1.2), (2, 0.2)],
 5    [(0, 1.2), (2, 1.5)],
 6    [(1, 1.5), (3, 3.2)],
 7    [(2, 1.4), (4, 1.4)],
 8    [(3, 1.4)],
 9    [(6, 2.3)],
10    []
11]
12graph = Graph.from_adjacency(graph)
13start_vertex = 2
14end_vertex = 0
15
16shortest_path = dijkstra_shortest_path(graph, start_vertex, end_vertex)
17print(shortest_path)

[2, 1, 0]