graph_tool.search.dijkstra_search

graph_tool.search.dijkstra_search(g, weight, source=None, visitor=<graph_tool.search.DijkstraVisitor object>, dist_map=None, pred_map=None, combine=<function <lambda>>, compare=<function <lambda>>, zero=0, infinity=inf)

Dijkstra traversal of a directed or undirected graph, with non-negative weights.

Parameters:

gGraph

Graph to be used.

weightEdgePropertyMap

Edge property map with weight values.

sourceVertex (optional, default: None)

Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order.

visitorDijkstraVisitor (optional, default: DijkstraVisitor())

A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of DijkstraVisitor.

dist_mapVertexPropertyMap (optional, default: None)

A vertex property map where the distances from the source will be stored.

pred_mapVertexPropertyMap (optional, default: None)

A vertex property map where the predecessor map will be stored (must have value type “int64_t”).

combinebinary function (optional, default: lambda a, b: a + b)

This function is used to combine distances to compute the distance of a path.

comparebinary function (optional, default: lambda a, b: a < b)

This function is use to compare distances to determine which vertex is closer to the source vertex.

zeroint or float (optional, default: 0)

Value assumed to correspond to a distance of zero by the combine and compare functions.

infinityint or float (optional, default: numpy.inf)

Value assumed to correspond to a distance of infinity by the combine and compare functions.

Returns:

dist_mapVertexPropertyMap

A vertex property map with the computed distances from the source.

pred_mapVertexPropertyMap

A vertex property map with the predecessor tree.

See also

bfs_search

Breadth-first search

dfs_search

Depth-first search

astar_search

\(A^*\) heuristic search algorithm

Notes

Dijkstra’s algorithm finds all the shortest paths from the source vertex to every other vertex by iteratively “growing” the set of vertices S to which it knows the shortest path. At each step of the algorithm, the next vertex added to S is determined by a priority queue. The queue contains the vertices in V - S prioritized by their distance label, which is the length of the shortest path seen so far for each vertex. The vertex u at the top of the priority queue is then added to S, and each of its out-edges is relaxed: if the distance to u plus the weight of the out-edge (u,v) is less than the distance label for v then the estimated distance for vertex v is reduced. The algorithm then loops back, processing the next vertex at the top of the priority queue. The algorithm finishes when the priority queue is empty.

The time complexity is \(O(E + V \log V)\).

The pseudo-code for Dijkstra’s algorithm is listed below, with the annotated event points, for which the given visitor object will be called with the appropriate method.

DIJKSTRA(G, source, weight)
  for each vertex u in V                      initialize vertex u
    d[u] := infinity
    p[u] := u
  end for
  d[source] := 0
  INSERT(Q, source)                           discover vertex s
  while (Q != Ø)
    u := EXTRACT-MIN(Q)                       examine vertex u
    for each vertex v in Adj[u]               examine edge (u,v)
      if (weight[(u,v)] + d[u] < d[v])        edge (u,v) relaxed
        d[v] := weight[(u,v)] + d[u]
        p[v] := u
        DECREASE-KEY(Q, v)
      else                                    edge (u,v) not relaxed
        ...
      if (d[v] was originally infinity)
        INSERT(Q, v)                          discover vertex v
    end for                                   finish vertex u
  end while
  return d

References

[dijkstra]

E. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1:269-271, 1959.

[dijkstra-bgl]

http://www.boost.org/doc/libs/release/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html

[dijkstra-wikipedia]

http://en.wikipedia.org/wiki/Dijkstra’s_algorithm

Examples

We must define what should be done during the search by subclassing DijkstraVisitor, and specializing the appropriate methods. In the following we will keep track of the discover time, and the predecessor tree.

class VisitorExample(gt.DijkstraVisitor):

    def __init__(self, name, time):
        self.name = name
        self.time = time
        self.last_time = 0

    def discover_vertex(self, u):
        print("-->", self.name[u], "has been discovered!")
        self.time[u] = self.last_time
        self.last_time += 1

    def examine_edge(self, e):
        print("edge (%s, %s) has been examined..." % \
            (self.name[e.source()], self.name[e.target()]))

    def edge_relaxed(self, e):
        print("edge (%s, %s) has been relaxed..." % \
            (self.name[e.source()], self.name[e.target()]))

With the above class defined, we can perform the Dijkstra search as follows.

>>> g = gt.load_graph("search_example.xml")
>>> name = g.vp["name"]
>>> weight = g.ep["weight"]
>>> time = g.new_vertex_property("int")
>>> dist, pred = gt.dijkstra_search(g, weight, g.vertex(0), VisitorExample(name, time))
--> Bob has been discovered!
edge (Bob, Eve) has been examined...
edge (Bob, Eve) has been relaxed...
--> Eve has been discovered!
edge (Bob, Chuck) has been examined...
edge (Bob, Chuck) has been relaxed...
--> Chuck has been discovered!
edge (Bob, Carlos) has been examined...
edge (Bob, Carlos) has been relaxed...
--> Carlos has been discovered!
edge (Bob, Isaac) has been examined...
edge (Bob, Isaac) has been relaxed...
--> Isaac has been discovered!
edge (Eve, Isaac) has been examined...
edge (Eve, Imothep) has been examined...
edge (Eve, Imothep) has been relaxed...
--> Imothep has been discovered!
edge (Eve, Carlos) has been examined...
edge (Eve, Chuck) has been examined...
edge (Eve, Bob) has been examined...
edge (Eve, Carol) has been examined...
edge (Eve, Carol) has been relaxed...
--> Carol has been discovered!
edge (Isaac, Bob) has been examined...
edge (Isaac, Chuck) has been examined...
edge (Isaac, Eve) has been examined...
edge (Chuck, Eve) has been examined...
edge (Chuck, Isaac) has been examined...
edge (Chuck, Imothep) has been examined...
edge (Chuck, Bob) has been examined...
edge (Carlos, Eve) has been examined...
edge (Carlos, Imothep) has been examined...
edge (Carlos, Bob) has been examined...
edge (Carlos, Alice) has been examined...
edge (Carlos, Alice) has been relaxed...
--> Alice has been discovered!
edge (Imothep, Carol) has been examined...
edge (Imothep, Carlos) has been examined...
edge (Imothep, Chuck) has been examined...
edge (Imothep, Eve) has been examined...
edge (Alice, Oscar) has been examined...
edge (Alice, Oscar) has been relaxed...
--> Oscar has been discovered!
edge (Alice, Dave) has been examined...
edge (Alice, Dave) has been relaxed...
--> Dave has been discovered!
edge (Alice, Carlos) has been examined...
edge (Carol, Eve) has been examined...
edge (Carol, Imothep) has been examined...
edge (Oscar, Alice) has been examined...
edge (Oscar, Dave) has been examined...
edge (Dave, Oscar) has been examined...
edge (Dave, Alice) has been examined...
>>> print(time.a)
[0 7 6 3 2 9 1 4 8 5]
>>> print(pred.a)
[0 3 6 0 0 1 0 0 1 6]
>>> print(dist.a)
[ 0.          8.91915887  9.27141329  4.29277116  4.02118246 12.23513866
  3.23790211  3.45487436 11.04391549  7.74858396]