Levit’s algorithm python3

levit.py

from math import inf


def levit(graph, start):
    min_weight = sum(sum(filter(lambda x: x < 0, row)) for row in graph) - 1
    size = len(graph)
    m0 = []      # checked
    m1 = [start]      # queue
    m1_urg = []  # urgent queue
    m2 = [i for i in range(size)]  # unchecked
    m2.remove(start)
    weight = [inf for _ in range(size)]
    weight[start] = 0
    path = [(i,) for i in range(size)]

    def evaluate(u, v, u_weight):
        if weight[v] > weight[u] + u_weight:
            weight[v] = weight[u] + u_weight
            path[v] = (v, *path[u])
            return True
        return False


graph = [[inf, 4, 4, inf, inf],
         [10, inf, inf, inf, inf],
         [10, 8, inf, 1, inf],
         [inf, 3, 2, inf, 2],
         [5, 7, 7, 7, inf]]
start = 0
stop = 4
weight, path = levit(graph, start)
path_from_start_to_stop = path[stop][::-1]