Dijkstra Algorithm

The Dijkstra algorithm is implemented to compute shortest paths in weighted graphs with non-negative edge weights.

It explores the graph starting from a source vertex and progressively expands the set of visited vertices using a priority queue (min-heap), always selecting the vertex with the smallest known distance.

The algorithm is used to compute shortest paths in weighted graphs where all edge weights are non-negative.

Unlike BFS, which assumes unit weights, Dijkstra takes edge weights into account.

All Dijkstra functions are convenience wrappers built on top of pygraphs.dijkstra().

Note

The algorithm assumes all edge weights are non-negative. Negative weights will produce incorrect results.

dijkstra(graph, start, *[, max_distance, ...])	[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.
dijkstra_distances(graph, start, *[, ...])	Compute shortest path distances from a source vertex to all reachable vertices using Dijkstra.
dijkstra_shortest_path(graph, start, end, *)	Compute the shortest path from a starting vertex to an ending vertex.
dijkstra_shortest_distance(graph, start, end, *)	Compute the shortest distance from a starting vertex to an ending vertex.
dijkstra_matrix(graph, *[, weight_key, ...])	Compute the shortest path distance matrix for all pairs of vertices.
dijkstra_k_annulus(graph, start, ...[, ...])	Return all vertices with distance in \([k_1, k_2]\) (ie \(\{v \in V | \text{dist}(i, v) \in [k_1, k_2]\}\)) where \(k_1\) and \(k_2\) are the specified inner and outer distances.
dijkstra_k_disk(graph, start, distance, *[, ...])	Return all vertices with distance lower than \(k\) (ie \(\{v \in V | \text{dist}(i, v) \leq k\}\)) where \(k\) is the specified distance.