Как добавляются потенциалы тогда в Hungarian algorithm?

Question

[alex_agaphe]

На коком этапе будет
( $u[i]=v[i]=0$  for all  $i$ ),
Следовательно H пустой
Как добавляются потенциалы тогда?
https://cp-algorithms.com/graph/hungarian-algorith...

Answer 1

[Wataru]

вы ссылку-то свою вообще читали?

( $u[i]=v[i]=0$  for all  $i$ ),

В начале. Вы начинаете с нулевых потенциалов, потом увеличиваете их как описанно в алгоритме, пока можете. Попутно обновляя множество H.

Кстати, даже при нулевых потенциалах H может быть не пустым, если в матрице есть нули.

Comments

[alex_agaphe]

оно пустое а дельта вычисляется толь для ребер в левой стгороне H

дельта вычислется по правилам для уже посещенных вершин - а если потенциал равен нулю или граф полный?
https://cp-algorithms.com/graph/hungarian-algorith...

[Wataru]

alex_agaphe, Если потенциал равен нулю и, допустим, нулевых значений в A нет, тогда H пустое вообще. Жестких ребер в графе нет вообще. Никакой удлинняющей цепочки найти нельзя, потому что там должны быть ребра из H и M, а у нас они оба пустые в начале. Обход в графе обойдет все вершины слева и ни одной вершины справа. Z1={1..N}, Z2={}. Поэтому при вычислении дельта вы обходите вообще все значения матрицы. Читайте формулу внимательно, там все j НЕ принадлежащие Z2.

[alex_agaphe]

Wataru, они принадлежат Z1 это же подмножество всех ребер из леввой стороны для H

[Wataru]

alex_agaphe, нет, z1 - это подмножество вершин в левой доле.