new_contents: from sys import maxint
  class BellmanFord( object ):
   
    def __init__( self ):
        '''
        Constructor
        '''
   
    def singleSourceShortestPath( self, weight, source ) :
      # auxiliary constants
      SIZE = len( weight )
      EVE = -1; # to indicate no predecessor
      INFINITY = maxint
   
      # declare and initialize pred to EVE and minDist to INFINITY
      pred = [EVE] * SIZE
      minDist = [INFINITY] * SIZE
   
      # set minDist[source] = 0 because source is 0 distance from itself.
      minDist[source] = 0
   
      # relax the edge set V-1 times to find all shortest paths
      for i in range( 1, SIZE - 1 ):
        for v in range( SIZE ):
          for x in self.adjacency( weight, v ):
            if minDist[x] > minDist[v] + weight[v][x]:
              minDist[x] = minDist[v] + weight[v][x]
              pred[x] = v
   
      # detect cycles if any
      for v in range( SIZE ):
        for x in self.adjacency( weight, v ):
          if minDist[x] > minDist[v] + weight[v][x]:
            raise Exception( "Negative cycle found" )
   
      return [pred, minDist]
   
   
    #=====================================================================
    # Retrieve all the neighbors of vertex v.
    #=====================================================================
    def adjacency( self, G, v ) :
      result = []
      for x in range( len( G ) ):
        if G[v][x] is not None:
          result.append( x )
   
      return result;
  
subject: Create bellman_ford.py