rustworkx.digraph_dijkstra_search

digraph_dijkstra_search(graph, source=None, weight_fn=None, visitor=None)

Dijkstra traversal of a directed 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 a StopSearch 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 raising PruneSearch.

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.PyDiGraph()
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.digraph_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 the finish_vertex event.

Parameters:

• graph (PyDiGraph) – 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 a Sequence[int] or None.

• 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 of None as a backwards compatibility artifact (to preserve argument ordering from an earlier version) but it is a required argument and will raise a TypeError if not specified.