pygraphs.dijkstra_distances#

dijkstra_distances(graph, start, *, max_distance=None, weight_key='weight', _skip_check=False)[source]#

Compute shortest path distances from a source vertex to all reachable vertices using Dijkstra.

Parameters:

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

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

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

  • 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 list of float representing the shortest path distances from the starting vertex to all other vertices in the graph. The length of the output list is equal to the number of vertices in the graph. Unreachable vertices have distance of -1.0.

Return type:

List[float]

See also

pygraphs.dijkstra()

Core implementation of Dijkstra.

pygraphs.dijkstra_matrix()

Compute the shortest path distance matrix for all pairs of vertices in the graph using Dijkstra.

Examples

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

../../_images/weighted_graph.png

Disconnected and weighted graph with 7 vertices for Dijkstra example. Distance from vertex 0 to vertex 4 is 4.8.#

 1from pygraphs import dijkstra_distances, 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
14
15distances = dijkstra_distances(graph, start_vertex)
16print(distances)

[0.0, 1.2, 0.2, 3.4, 4.8, -1.0, -1.0]

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. Distance from vertex 2 to vertex 0 is 2.7.#

 1from pygraphs import dijkstra_distances, 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
14
15distances = dijkstra_distances(graph, start_vertex)
16print(distances)

[2.7, 1.5, 0.0, 3.2, 4.6, -1.0, -1.0]