#!/usr/bin/env python
#Author: Shriphani Palakodety

#Bellman Ford Implementation. Look it up on wikipedia.

#import graph #import my stupid graph class

class Graph():
    '''Describes a graph'''

    def __init__(self, nodes_list, edge_dict):

        self.V = nodes_list
        self.E = edge_dict


distances = {}
parents = {}

def Initialize(graph, start):
    '''Prepares the graph for the bellman-ford algorithm'''
    for vertex in graph.V:
        if graph.E.has_key((start, vertex)):
            distances[vertex] = 9999999e6

    distances[start] = 0
    parents[start] = None

    
    
def Bellman_Ford(graph, start):

    Initialize(graph, start) #first initialize the graph

    for i in xrange(len(graph.V) - 1):
        for edge in graph.E.keys():
            if (graph.E[edge] + distances[edge[0]]) < distances[edge[1]]:
                distances[edge[1]] = graph.E[edge] + distances[edge[0]]
                parents[edge[1]] = edge[0]

    #one final check for negative weight cycles.

    for edge in graph.E.keys():
        if (graph.E[edge] + distances[edge[0]]) < distances[edge[1]]:
            distances[edge[1]] = graph.E[edge] + distances[edge[0]]
            parents[edge[1]] = edge[0]
            return edge[1] #return here since, a negative weight cycle is detected

    return None #return none on successful completion.