1 Тема от witua Отредактировано witua (2010-06-13 21:39:54)

  • witua
  • Участник
  • Неактивен
  • Откуда: Львов
  • Зарегистрирован: 2010-01-26
  • Сообщений: 13

Тема: Цикл

Как найти минимальный цикл в взвешенном неориентированом графе?

2 Ответ от MBo

  • MBo
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-10-05
  • Сообщений: 52

Re: Цикл

http://forum2007.algolist.ru/showflat.p … age/0#8051

3 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: Цикл

http://www.fi.muni.cz/ceoi1999/trip/TRIP.C  - O(N^3)

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

4 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Цикл

Можно за O(VElogV). Если ребер порядка вершин, то в сумме будет O(N^2logN).