from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import numpy as np


def update_distance(v, v_neighbor, 
                    w_graph_d, distance_d, previous_d):
    if (distance_d[v_neighbor] > 
            distance_d[v] + w_graph_d[v][v_neighbor]):
        distance_d[v_neighbor] = (
            distance_d[v] + w_graph_d[v][v_neighbor])
        previous_d[v_neighbor] = v
    return distance_d, previous_d 


def bellman_ford(w_graph_d, start_vertex):
    """Bellman-Ford algorithm for single-source shortest path problem
    in "weighted negative" graph, G(V, E).

    Time complexity: O(|V|*|E|).
    Space complexity: O(|V|).
    """
    distance_d = {v: np.inf for v in w_graph_d.keys()}
    previous_d = {v: None for v in w_graph_d.keys()}

    distance_d[start_vertex] = 0

    n = len(w_graph_d.keys())
    # Run through |V| - 1 times.
    for i in xrange(1, n):
        # Run through all edges.
        for v in w_graph_d.keys():
            for v_neighbor in w_graph_d[v].keys():
                distance_d, previous_d = update_distance(
                    v, v_neighbor, w_graph_d, distance_d, previous_d)
    
    # Check negative cycle by update distance once more and check if any diff.
    _distance_d = distance_d.copy()
    _previous_d = previous_d.copy()

    for v in w_graph_d.keys():
        for v_neighbor in w_graph_d[v].keys():
            _distance_d, _previous_d = update_distance(
                v, v_neighbor, w_graph_d, _distance_d, _previous_d)
            if _distance_d != distance_d:
                raise ValueError('Negative cycle exists.')

    return distance_d, previous_d


def main():
    w_graph_d = {
        's': {'a': 2, 'b': 6},
        'a': {'b': 3, 'c': 1},
        # 'b': {'a': -5, 'd': 2}, # With negative cycle.
        'b': {'a': -2, 'd': 2},
        'c': {'b': 1, 'e': 4, 'f': 2},
        'd': {'c': 3, 'f': 2},
        'e': {},
        'f': {'e': 1}
    }
    start_vertex = 's'

    distance_d, previous_d = bellman_ford(w_graph_d, start_vertex)
    print('distance_d: {}'.format(distance_d))
    print('previous_d: {}'.format(previous_d))


if __name__ == '__main__':
    main()

@@ -128,16 +128,17 @@
 p%0A%0A%0Adef 
+_
 update_d
@@ -161,16 +161,17 @@
 ghbor, %0A
+ 
         
@@ -218,16 +218,62 @@
 ous_d):%0A
+    %22%22%22Update distance with previous node.%22%22%22%0A
     if (
@@ -514,16 +514,548 @@
 us_d %0A%0A%0A
+def _check_negative_cycle(distance_d, previous_d, w_graph_d):%0A    %22%22%22Check negative cycle.%0A%0A    Update distance once more and check if any diff.%0A    %22%22%22%0A    _distance_d = distance_d.copy()%0A    _previous_d = previous_d.copy()%0A%0A    for v in w_graph_d.keys():%0A        for v_neighbor in w_graph_d%5Bv%5D.keys():%0A            _distance_d, _previous_d = _update_distance(%0A                v, v_neighbor, w_graph_d, _distance_d, _previous_d)%0A            if _distance_d != distance_d:%0A                raise ValueError('Negative cycle exists.')%0A%0A%0A
 def bell
@@ -1425,126 +1425,141 @@
     
-n = len(w_graph_d.keys())%0A    # Run through %7CV%7C - 1 times.%0A    for i in xrange(1, n):%0A        # Run through all edges.
+# Run through %7CV%7C - 1 times, in each iteration update all edges's distances.%0A    n = len(w_graph_d.keys())%0A    for i in xrange(1, n):
 %0A   
@@ -1674,32 +1674,33 @@
 d, previous_d = 
+_
 update_distance(
@@ -1806,224 +1806,42 @@
 cle 
-by update distance once more and check 
 if any
- diff
 .%0A    _
-distance_d = distance_d.copy()%0A    _previous_d = previous_d.copy()%0A%0A    for v in w_graph_d.keys():%0A        for v_neighbor in w_graph_d%5Bv%5D.keys():%0A            _
+check_negative_cycle(
 dist
@@ -1840,33 +1840,32 @@
 cle(distance_d, 
-_
 previous_d = upd
@@ -1862,195 +1862,19 @@
 us_d
- = update_distance(%0A                v, v_neighbor, w_graph_d, _distance_d, _previous_d)%0A            if _distance_d != distance_d:%0A                raise ValueError('Negative cycle exists.'
+, w_graph_d
 )%0A%0A 

Refactor to _check_negative_cycle()