pygraphs.dijkstra_shortest_distance#

dijkstra_shortest_distance(graph, start, end, *, weight_key='weight', 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 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:

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

Return type:

float

See also

pygraphs.dijkstra()

Core implementation of Dijkstra.

pygraphs.dijkstra_distances()

Compute the shortest path distances from a starting vertex to all other vertices in the graph.

Examples

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

 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_dist = dijkstra_shortest_distance(graph, start_vertex, end_vertex)
17print(shortest_dist)

4.8

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) with distance 2.7.#

 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_dist = dijkstra_shortest_distance(graph, start_vertex, end_vertex)
17print(shortest_dist)

2.7