shortest_path_bellman_ford(graph,
source)
|
|
Return the shortest path distance between the source node and all
other nodes in the graph using Bellman-Ford's algorithm.
This algorithm is useful when you have a weighted (and obviously a
directed) graph with negative weights.
- Parameters:
graph (digraph) - Digraph
source (node) - Source node of the graph
- Returns: tuple
- A tuple containing two dictionaries, each keyed by target nodes.
(same as shortest_path function that implements Dijkstra's
algorithm)
-
Shortest path spanning tree
-
Shortest distance from given source to each target node
- Raises:
NegativeWeightCycleError - raises if it finds a negative weight cycle. If this condition is
met d(v) > d(u) + W(u, v) then raise the error.
Attention:
The algorithm can detect negative weight cycles and will raise an
exception. It's meaningful only for directed weighted graphs.
See Also:
shortest_path
|