Bellman-Ford algorithm for shortest paths

bellman_ford.py

import numpy as np
import numba

@numba.jit
def bellman_ford(graph, start_vertex):
    n = len(graph.nodes)
    A = np.zeros((n+1, n))
    A[0, :] = np.inf
    A[0, start_vertex] = 0
    
    for i in range(1, n+1):
        for v in range(n):
            
            # convenient to store costs in a matrix for vectorization
            new_path_costs = A[i-1, graph.incoming_neighbors[v]] +\
                graph.edge_costs[graph.incoming_neighbors[v], v]        
            
            A[i, v] = min(A[i-1, v], min(new_path_costs))
        
        # stopping early
        if i < n-1 and (A[i, :] == A[i-1, :]).all():
            return A[i, :]
            
    if (A[-2, :] == A[-1, :]).all():
        return A[n-1, :]
    
    else:
        raise ValueError('Negative cycle present')