Транспортная задача: нахождение цикла (замкнутого пути)

[Cash]

При решении транспортной задачи как в методе потенциалов так и в методе падающего камня ключевым моментом при реализации является нахождение цикла (замкнутого пути). К сожалению, не нашел ни одного толкового описания алгоритма, готового к реализации. Например, для нахождения цикла предлагается следующий метод:

Цитата:

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

И это самое лучшее, что смог найти
В результате нескольких часов страданий придумал следующую эвристику:
Отмечаем ячейку, для которой нам нужно найти цикл и все ячейки опорного плана. Вычеркиваем все строки и столбцы с единственным отмеченным элементом до тех пор пока не сможем ничего вычеркнуть. В итоге у нас останутся отмеченными только узлы искомого пути.
Проверял на тестовых данных - вроде работает. Это верный алгоритм?

И если у кого есть ссылка на работающий алгоритм решения транспортной задачи - буду весьма благодарен...

[Shadow]

Я когда-то писал программу для транспортной задачи...на бейсик. Поиск пути осуществлял с помощью 2 функций, обращающиеся друг к другу (наверное не очень оптимизированное, зато ленивое решение) Функции HLine, VLine возвращали существует ли путь от некоторой ячейки до стартовой ячейки с первой горизонтальной/вертикальной чертой. Что-то вроде:

Function HLine(FromX,FromY) as Boolean
If FromY=StartY And FromX<>StartX Then
 HLine=True
 AddPoint(FromX,FromY)
Else
 Hline=False
 For J=1 To Columns
  If J<>FromX and not M(FromY,J).Empty Then
   If VLine(J,FromY) Then
    HLine=True
    AddPoint(FromX,FromY)
    Exit For
   End If
  End If
 Next J
End If
End Function

Аналогичная VLine. Работало как-то.

[K-3]

Кажется, что информацию удобно хранить в виде двудольного графа. Вершины одной доли соответствуют "складам", а второй - "магазинам". Соединяем две вершины ребром, если соответсвующая переменная входит в базу. Циклы в таблице будут соответствовать циклам в графе.