Dato un grafo orientato e pesato G=(V, E) con pesi positivi, cioè w(u, v) > 0 per ogni (u, v) ∈ E, si vuole determinare se esiste in G un ciclo c ≡ <x0, x1, ... xq> (con x0 = xq) per cui sia soddisfatta la seguente condizione:
Si sviluppi un algoritmo per risolvere questo problema, se ne discuta la correttezza e si determini la sua complessità computazionale. (Suggerimento: si cerchi di ricondurre il problema dato ad uno noto)