Почему не работает алгоритм Форда-Фалкерсона?

Question

[Perflex_er]

Есть такой код,взял с этого видео на ютуб
Ссылка удалена модератором.

Думаю,что можно реализовать для такого графа



Не понимаю в чем проблема ,выдает такую ошибку :
IndexError: list index out of range

import math


def get_max_vertex(k, V, S):
    m = 0   # наименьшее допустимое значение
    v = -1
    for i, w in enumerate(V[k]):
        if i in S:
            continue

        if w[2] == 1:   # движение по стрелке
            if m < w[0]:
                m = w[0]
                v = i
        else:           # движение против стрелки
            if m < w[1]:
                m = w[1]
                v = i

    return v


def get_max_flow(T):
    w = [x[0] for x in T]
    return min(*w)


def updateV(V, T, f):
    for t in T:
        if t[1] == -1:  # это исток
            continue

        sgn = V[t[2]][t[1]][2]  # направление движения

        # меняем веса в таблице для (i,j) и (j,i)
        V[t[1]][t[2]][0] -= f * sgn
        V[t[1]][t[2]][1] += f * sgn

        V[t[2]][t[1]][0] -= f * sgn
        V[t[2]][t[1]][1] += f * sgn


V = [[[0,0,1], 	[4,2,1],	[0,0,1],	[6,3,1],	[4,2,1],	[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1]],
[[4,2,-1],	[0,0,1],	[4,3,1],	[5,3,-1],	[0,0,1],	[0,0,1],	[0,0,1],	[3,2,-1],	[0,0,1],	[0,0,1]],
[[0,0,1],	[4,3,-1],	[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[3,0,-1],	[0,0,1],	[3,3,1]],
[[6,3,-1],	[5,3,1],	[0,0,1],	[0,0,1],	[3,1,-1],	[0,0,1],	[5,4,1],	[0,0,1],	[4,3,-1],	[0,0,1]],
[[4,2,-1],	[0,0,1],	[0,0,1],	[3,1,1],	[0,0,1],	[3,2,1],	[3,1,-1],	[0,0,1],	[0,0,1],	[0,0,1]],
[[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[3,2,-1],	[0,0,1],	[3,1,1],	[0,0,1],	[0,0,1],	[3,1,1]],
[[0,0,1],	[0,0,1],	[0,0,1],	[5,4,-1],	[3,1,1],	[3,1,-1],	[0,0,1],	[0,0,1],	[4,4,1],	[0,0,1]],
[[0,0,1],	[3,2,-1],	[3,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[0,0,1],	[3,1,1],	[5,1,1]],
[[0,0,1],	[0,0,1],	[0,0,1],	[4,3,1],	[0,0,1],	[0,0,1],	[4,4,-1],	[3,1,-1],	[0,0,1],	[3,2,1]]]

N = 10  # число вершин в графе
init = 0    # вершина истока (нумерация с нуля)
end = 9     # вершина стока
Tinit = (math.inf, -1, init)      # первая метка маршруто (a, from, vertex)
f = []      # максимальные потоки найденных маршрутов

j = init
while j != -1:
    k = init  # стартовая вершина (нумерация с нуля)
    T = [Tinit]  # метки маршрута
    S = {init}  # множество просмотренных вершин

    while k != end:     # пока не дошли до стока
        j = get_max_vertex(k, V, S)  # выбираем вершину с наибольшей пропускной способностью
        if j == -1:         # если следующих вершин нет
            if k == init:      # и мы на истоке, то
                break          # завершаем поиск маршрутов
            else:           # иначе, переходим к предыдущей вершине
                k = T.pop()[2]
                continue

        c = V[k][j][0] if V[k][j][2] == 1 else V[k][j][1]   # определяем текущий поток
        T.append((c, j, k))    # добавляем метку маршрута
        S.add(j)            # запоминаем вершину как просмотренную

        if j == end:    # если дошди до стока
            f.append(get_max_flow(T))     # находим максимальную пропускную способность маршрута
            updateV(V, T, f[-1])        # обновляем веса дуг
            break

        k = j

F = sum(f)
print(f"Максимальный поток равен: {F}")

Comments

[mayton2019]

В какой строке эта ошибка?

Python обычно пишет. Это помогло бы с анализом ситуации. Не всем охота разбирать
всю дискретную математику просто лишь для того чтобы ответить на вопрос по Python.

И тема топика все таки Python. Мы обсуждаем код на Python. И нам нужны сведенья по ошибке
чтоб не терять зря врмя на поиски ее там где ее нет.

[Wataru]

Perflex_er
Какая-то очень кривая реализация Форда-Фолкерсона. Что за 3 числа в матрице смежности? Пропускная способность/заполненность/цена?

Поиск пути вообще через непонятное место сделан. Это что-то типа нерекурсивного обхода в глубину, что ли? Перепишите рекурсивно, попроще.

Answer 1

[kalapanga]

А тут нечего и понимать. Подобное выясняется отладкой.
На строке, в которой происходит ошибка, смотрите значения переменных, соображаете, значение какой из них оказалось за пределами допустимого и почему оно таким оказалось.

Comments

[Perflex_er]

В этом и суть вопроса, что я не могу где выходит за предел
Ошибка выдается на 37 и 81 строках
V[t[1]][t[2]][0] -= f * sgn
updateV(V, T, f[-1])
т.е. когда мы меняем значение веса дуги. Но какие значения я должен выбрать, чтобы понять где ошибка , я не понимаю.

[kalapanga]

Видимо в первом случае надо посмотреть значения t[1] и t[2], а во втором на сам f - есть ли в нём что-то.

[Perflex_er]

kalapanga, Если Вам интересно, то я в таблице не указал нижнюю строку, т.е значения для Y(стока) т.к. думал,что сток не влияет на результат(так оно и есть), но код выходил за пределы)