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)[source]#
Dijkstra traversal of a directed or undirected graph, with non-negative weights.
- Parameters:
- g
Graph Graph to be used.
- weight
EdgePropertyMap Edge property map with weight values.
- source
Vertex(optional, default:None) Source vertex. If unspecified, all vertices will be traversed, by iterating over starting vertices according to their index in increasing order.
- visitor
DijkstraVisitor(optional, default:DijkstraVisitor()) A visitor object that is invoked at the event points inside the algorithm. This should be a subclass of
DijkstraVisitor.- dist_map
VertexPropertyMap(optional, default:None) A vertex property map where the distances from the source will be stored.
- pred_map
VertexPropertyMap(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.
- g
- Returns:
- dist_map
VertexPropertyMap A vertex property map with the computed distances from the source.
- pred_map
VertexPropertyMap A vertex property map with the predecessor tree.
- dist_map
See also
bfs_searchBreadth-first search
dfs_searchDepth-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]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]