pygraphs.dijkstra#

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

[core function] Perform a Dijkstra algorithm to compute the shortest path distances from a starting vertex to all other vertices in a weighted graph, and to keep track of the parent vertices for each visited vertex.

Warning

No tests are performed to check if the input graph is valid (e.g., if the graph contains self-loops, if the graph contains invalid vertex indices, …). The behavior of the function is undefined if the input graph is not valid.

Parameters:

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

  • start (Integral) – The starting vertex index.

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

  • parents (Dict[int, int]) – A dictionary mapping each visited vertex index to its parent vertex index in the Dijkstra tree. The starting vertex will have a parent of None.

  • distances (Dict[int, float]) – A dictionary mapping each visited vertex index to its shortest path distance from the starting vertex. The starting vertex will have a distance of 0.

Return type:

Tuple[Dict[int, int], Dict[int, float]]

Notes

The function uses a Dijkstra approach to compute the shortest path distances, which is efficient for weighted graphs. The time complexity is \(O((V + E)\log V\), where \(V\) is the number of vertices and \(E\) is the number of edges in the graph.

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, 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
15parent, distance = dijkstra(graph, start_vertex)
16print("Parent:", parent)
17print("Distance:", distance)

Parent: {0: None, 1: 0, 2: 0, 3: 2, 4: 3}
Distance: {0: 0, 1: 1.2, 2: 0.2, 3: 3.4, 4: 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. Distance from vertex 2 to vertex 0 is 2.7.#

 1from pygraphs import dijkstra, 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
15parent, distance = dijkstra(graph, start_vertex)
16print("Parent:", parent)
17print("Distance:", distance)

Parent: {2: None, 1: 2, 3: 2, 0: 1, 4: 3}
Distance: {2: 0.0, 1: 1.5, 3: 3.2, 0: 2.7, 4: 4.6}