Bellman-Ford

#Uses python3

import sys
import math
import doctest
import copy
import numpy as np


def parse_input(inpt):
    """
    Parse the graph and weights from a string

    param inpt: a string where the fist line is the number of nodes and edges and
    the rest are edges with weights
    return adj: int, represents the edges
    return cost: floats, represents cost the weights
    """
    data = list(map(int, inpt.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3]))
    data = data[3 * m:]
    adj = [[] for _ in range(n)]
    cost = [[] for _ in range(n)]
    for ((a, b), w) in edges:
        adj[a - 1].append(b - 1)
        cost[a - 1].append(w)

    return adj, cost


def negative_cycle(adj, cost, correctness=False):
    """
    detect negative cycle in a graph
    reference: https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf
    param adj: list of list, index represent nodes, and values the edges starting from them
    param cost: list of list, index represent nodes, and values the corresponding weights of edges
    return 0 or 1: 1 represents that there is at least 1 negative cycle in the graph
    >>> negative_cycle([[1], [2], [0], [0]], [[-5], [2], [1], [2]])
    1
    >>> negative_cycle([[1], [2], [3], [0]], [[2], [3], [1], [2]])
    0
    >>> negative_cycle([[1, 3], [2], [], [2]], [[3, 7], [4], [], [5]])
    0
    >>> negative_cycle([[1, 2], [2], [], [4], [5], [3]], [[1, 1], [1], [], [-1], [-2], [1]])
    1
    >>> negative_cycle([[1, 3], [2], [4], [2], [5], [3]], [[9, 5], [4], [-3], [3], [1], [5]])
    0
    >>> negative_cycle([[1, 3], [2], [4], [2], [5], [3]], [[9, 5], [4], [-3], [3], [1], [-5]])
    1
    """
    vertex_num = len(adj)
    if correctness:
        memoization_table = np.matrix(np.ones((vertex_num, vertex_num)) * 10**7)
        memoization_table[:, 0] = 0
    else:
        memoization_table = [10**7] * vertex_num
        memoization_table[0] = 0

    for i in range(1, vertex_num):
        for u in range(0, vertex_num):
            for j, v in enumerate(adj[u]):
                if correctness:
                    memorzation_table[i, v] = min(memorzation_table[i, v], memoization_table[i-1, u]+cost[u][j])
                else:
                    memorzation_table[v] = min(memorzation_table[v], memoization_table[u]+cost[u][j])

        # print(memoization_table)

    for u in range(0, vertex_num):
        for j, v in enumerate(adj[u]):
            if correctness and memoization_table[i, v] > memoization_table[i, u]+cost[u][j]:
                return 1
            elif not correctness and memoization_table[v] > memoization_table[u]+cost[u][j]:
                return 1

    return 0


if __name__ == '__main__':
    inpt = sys.stdin.read()
    adj, cost = parse_input(inpt)
    print(negative_cycle(adj, cost))
    doctest.testmod()