2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Цикл отрицательной стоимости в двудольном графе
Сообщение26.05.2011, 21:11 


26/05/11
2
Подскажите, как создать оптимальный алгоритм поиска цикла отрицательной стоимости, учитывая, что исходный граф является двудольный. Пробовал алгоритм Флойда (цикл отриц. стоимости сущ., если в ходе работы алгоритма на диагонали матрицы смежности появилось отрицательное значение) и Беллмана-Форда (цикл отриц. сотоимости сущ., если после выполнения |V| - 1 итерации алгоритма выполняется еще одна). Желательна трудоемкость не хуже O(|V|*|E|) на матрице, где элемент (i, j) - вес дуги из i-ой вершины одной доли в j-ую вершину другой, причем если (i, j) >= 0, то дуга соединяет i-ю вершины первой доли с j-ой вершиной второй доли, (i, j) < 0, то дуга соединяет i-ю вершины второй доли с j-ой вершиной первой доли (вес все равно остается отрицательным).
Все началось с задачи о нахождении минимального/максимального взвешенного паросочетания.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group