Изменения

Перейти к: навигация, поиск
Наивный способ
'''func''' findMinCycleBinarySearch('''int''' l, '''int''' r)
<!-----<font color="green">// добавляем мнимую вершину находим среднюю величину <tex>sm</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
m = (l + r) / 2
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого вычитаем её из веса каждого ребра в каждую вершину графасети</font>--------->
'''for''' e '''in''' edges
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
e.weight -= m
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
'''while''' l > r - 1
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
'''if''' <tex>\exists</tex>C : M(C) < 0 <!--- cho-t xz za4em C: mb exists? eee ugadala)0))--->
<!----- <font color="green">// добавляем мнимую вершину если есть отрицательный цикл, то веса циклов находятся в диапазоне <tex>s[l;m]</tex> и проводим рёбра нулевого веса в каждую вершину графа // рассмотрим этот промежуток</font>--------->
findMinCycleBinarySearch (l, m)
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
'''else'''
<!----- <font color="green">// добавляем мнимую вершину в противном случае запускаем двоичный поиск на отрезке <tex>s[m;r]</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
findMinCycleBinarySearch (m, r)
<!-----<font color="green">// добавляем мнимую вершину <tex>s</tex> и проводим рёбра нулевого веса в каждую вершину графа</font>--------->
===Продвинутый алгоритм===
693
правки

Навигация