def 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.
    
    @attention: The algorithm can detect negative weight cycles and will raise 
    an exception. It's meaningful only for directed weighted graphs.
    
    @see: shortest_path
    
    @type graph: digraph
    @param graph: Digraph
    
    @type source: node
    @param source: Source node of the graph
    
    @raise 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. 
    
    @rtype: tuple 
    @return: A tuple containing two dictionaries, each keyed by target nodes.
    (same as shortest_path function that implements Dijkstra's algorithm)
        1. Shortest path spanning tree
        2. Shortest distance from given source to each target node
    """
    # initialize the required data structures       
    distance = {source : 0}
    predecessor = {source : None}
    
    # iterate and relax edges    
    for i in range(1,graph.order()-1):
        for src,dst in graph.edges():
            if (src in distance) and (dst not in distance):
                distance[dst] = distance[src] + graph.edge_weight((src,dst))
                predecessor[dst] = src
            elif (src  in distance) and (dst in distance) and \
            distance[src] + graph.edge_weight((src,dst)) < distance[dst]:
                distance[dst] = distance[src] + graph.edge_weight((src,dst))
                predecessor[dst] = src
                
    # detect negative weight cycles
    for src,dst in graph.edges():
        if src in distance and \
           dst in distance and \
           distance[src] + graph.edge_weight((src,dst)) < distance[dst]:
            raise NegativeWeightCycleError("Detected a negative weight cycle on edge (%s, %s)" % (src,dst))
        
    return predecessor, distance
        
#Heuristics search
dataset/ETHPy150Open pmatiello/python-graph/core/pygraph/algorithms/minmax.py/shortest_path_bellman_ford/original