22 maggio 2024 - esercizio 2

[Elia-Belli]

[CarloDaRomadev]

Prima parte:

def floyd_warshall_mod(x, vis, stack) -> bool:
    vis[x] = 1
    stack.push(x)
    for w in x.adiacenti:
        if vis[w] ≠ 1:
            floyd_warshall_mod(w, vis, stack)
        else:
            count = 0
            u = w
            while stack.top() ≠ w:
                y = stack.pop()
                count += c(y, u)
                u = x
                if count < 0:
                    return True
    return False

def floyd_warshall_mod_aux(G) -> bool:
    x = random(V(G))
    if floyd_warshall_mod(x, [0, ..., 0], ∅):
        return True
    return False

T(n) = O(n+m)

Seconda parte:

def min_ciclo_aux(G) -> int:
    m = +∞
    for x in V(G):
        e = min_ciclo(x, x, ∅, [0, ..., 0], m)
        m = min(m, e)
    return m

def min_ciclo(R, x, stack, vis, m) -> int:
    vis[x] = 1
    stack.append(x)

    for w in x.adiacenti:
        if vis[w] == 0:
            min_ciclo(R, w, stack, vis, m)
        if w == R:
            count = 0
            num = 0
            u, v, e = null
            while stack.top() ≠ w:
                n++
                if |u.adiacenti| > 1:
                    vis[u] = 1
                    e = w
            else:
                if e ≠ null:
                    vis[u] = 0
                x = stack.pop()
                count += c(u, v)
                u = x
                count < 0
            
            if m > num:
                m = num
            if e ≠ null:
                min_ciclo(R, e, stack, vis, m)

T(n) = O(2^n)
questo è troppo elevato per la richiesta, sono passato quindi ad un'altra strategia:

def MIN_CICLO(G):
    for i in range(3, n):
        for v in V(G):
            x = v
            j = 0
            while True:
                padri = [-1, ..., -1], padri[x] = x, conto = 0
                while j < i:
                    if  v.ADIACENTI[0] != NULL:
                        u = v.ADIACENTI[0]
                        v.ADIACENTI.remove(0)
                        padri[u] = v
                        conto += c(v, u)
                        v = u
                        y = v
                    else:
                        conto -= c(padri[v], v)
                        v = padri[v]
                        j -= 1
                        
               if x == y and conto < 0:
                    return i
               if j == 0:
                    break
               else:
                   j-= 1
                   v = padri[v]
                   conto -= c(padri[v], v)
    return -1

questo algoritmo cerca per ogni numero i da 3 a n se è presente un ciclo di peso negativo di i nodi, se lo trova ritorna il valore di i

Il costo di questo algoritmo è O((n^2)*m)
dato che m < n(n-1)
il costo sarà O(n^4)

perché il primo for è ripetuto n volte, il for più interno è ripetuto n volte, il while true sarà ripetuto al massimo su tutti gli archi, cioè m