Note
This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.
rustworkx.graph_dijkstra_search#
- graph_dijkstra_search(graph, source=None, weight_fn=None, visitor=None)#
Dijkstra traversal of an undirected graph with several source vertices.
Pseudo-code for the Dijkstra algorithm with a single source vertex is listed below with annotated event points at which a method of the given
DijkstraVisitor
is called.# G - graph, s - single source node, weight - edge cost function DIJKSTRA(G, s, weight) let score be empty mapping let visited be empty set let Q be a priority queue score[s] := 0.0 PUSH(Q, (score[s], s)) # only score determines the priority while Q is not empty cost, u := POP-MIN(Q) if u in visited continue PUT(visited, u) # event: discover_vertex(u, cost) for each _, v, w in OutEdges(G, u) # v - target vertex, w - edge weight ... # event: examine_edge((u, v, w)) if v in visited continue next_cost = cost + weight(w) if {(v is key in score) and (score[v] <= next_cost)} # event: edge_not_relaxed((u, v, w)) ... else: # v not scored or scored higher score[v] = next_cost # event: edge_relaxed((u, v, w)) PUSH(Q, (next_cost, v)) end for # event: finish_vertex(u) end while
For several source nodes, the Dijkstra algorithm is applied on source nodes by the given order.
If an exception is raised inside the callback method of the
DijkstraVisitor
instance, the graph traversal will be stopped immediately. You can exploit this to exit early by raising aStopSearch
exception, in which case the search function will return but without raising back the exception. You can also prune part of the search tree by raisingPruneSearch
.In the following example we find the shortest path from vertex 0 to 5, and exit the visit as soon as we reach the goal vertex:
import rustworkx as rx from rustworkx.visit import DijkstraVisitor, StopSearch graph = rx.PyGraph() graph.extend_from_edge_list([ (0, 1), (0, 2), (0, 3), (0, 4), (1, 3), (2, 3), (2, 4), (4, 5), ]) class PathFinder(DijkstraVisitor): def __init__(self, start, goal): self.start = start self.goal = goal self.predecessors = {} def get_path(self): n = self.goal rev_path = [n] while n != self.start: n = self.predecessors[n] rev_path.append(n) return list(reversed(rev_path)) def discover_vertex(self, vertex, cost): if vertex == self.goal: raise StopSearch def edge_relaxed(self, edge): self.predecessors[edge[1]] = edge[0] start = 0 vis = PathFinder(start=start, goal=5) rx.graph_dijkstra_search(graph, [start], weight_fn=None, visitor=vis) print('Path:', vis.get_path())
Path: [0, 4, 5]
Note
Graph can not be mutated while traversing. Trying to do so raises an exception.
Note
An exception is raised if the
PruneSearch
is raised in thefinish_vertex
event.- Parameters:
graph (PyGraph) – The graph to be used.
source – An optional list of node indices to use as the starting nodes for the dijkstra search. If
None
or not specified then a source will be chosen arbitrarily and repeated until all components of the graph are searched. This can be aSequence[int]
orNone
.weight_fn – An optional weight function for an edge. It will accept a single argument, the edge’s weight object and will return a float which will be used to represent the weight/cost of the edge. If not specified, a default value of cost
1.0
will be used for each edge.visitor – A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of
DijkstraVisitor
. This has a default value ofNone
as a backwards compatibility artifact (to preserve argument ordering from an earlier version) but it is a required argument and will raise aTypeError
if not specified.