Encontrando um ciclo negativo no grafo

Você recebe um grafo direcionado e com pesos: $G$ com $N$ vértices e $M$ arestas. Encontre nele qualquer ciclo de peso negativo, se esse ciclo existir.

É conveniente usar algoritmos diferentes para resolver essas duas variações do problema; portanto, discutiremos os dois aqui.

Algoritmo de Bellman-Ford

O algoritmo de Bellman-Ford permite verificar se existe um ciclo de peso negativo no grafo e, se existir, é possível encontrar um desses ciclos.

Os detalhes do algoritmo estão descritos no artigo sobre o algoritmo de Bellman-Ford. Aqui descreveremos apenas sua aplicação para esse problema.

Faça $N$ iterações do algoritmo de Bellman-Ford. Se não houve alterações na última iteração, não há ciclo de peso negativo no grafo. Caso contrário, pegue um vértice cuja distância mudou até ele e vá através de seus ancestrais até encontrar um ciclo. Este ciclo será o ciclo desejado de peso negativo.

Implementação

struct Edge {
    int a, b, cost;
};

int n, m;
vector<Edge> edges;
const int INF = 1000000000;

void solve()
{
    vector<int> d(n);
    vector<int> p(n, -1);
    int x;
    for (int i = 0; i < n; ++i) {
        x = -1;
        for (Edge e : edges) {
            if (d[e.a] + e.cost < d[e.b]) {
                d[e.b] = d[e.a] + e.cost;
                p[e.b] = e.a;
                x = e.b;
            }
        }
    }

    if (x == -1) {
        cout << "Sem ciclo negativo.";
    } else {
        for (int i = 0; i < n; ++i)
            x = p[x];

        vector<int> cycle;
        for (int v = x;; v = p[v]) {
            cycle.push_back(v);
            if (v == x && cycle.size() > 1)
                break;
        }
        reverse(cycle.begin(), cycle.end());

        cout << "Ciclo negativo: ";
        for (int v : cycle)
            cout << v << ' ';
        cout << endl;
    }
}

Algoritmo de Floyd-Warshall

O algoritmo de Floyd-Warshall permite resolver a segunda variação do problema - encontrando todos os pares de vértices $(i, j)$ que não possuem um caminho mais curto entre eles (ou seja, existe um caminho de peso arbitrariamente pequeno).

Novamente, os detalhes podem ser encontrados no artigo de Floyd-Warshall, e aqui descrevemos apenas sua aplicação.

Execute o algoritmo Floyd-Warshall no grafo. Inicialmente $d[v][v] = 0$ para cada $v$. Porém, após a execução do algoritmo, $d[v][v]$ será menor que $0$ se houver um caminho de comprimento negativo de $v$ a $v$. Podemos usar isso para encontrar também todos os pares de vértices que não possuem um caminho mais curto entre eles. Nós iteramos sobre todos os pares de vértices $(i, j)$ e, para cada par, verificamos se eles têm um caminho mais curto entre eles. Para fazer isso, tente todas as possibilidades de um vértice intermediário $t$. $(i, j)$ não possui um caminho mais curto, se um dos vértices intermediários $t$ tiver $d[t][t] < 0$ (ou seja: $t$ faz parte de um ciclo de peso negativo) , $t$ pode ser alcançado de $i$ e $j$ pode ser alcançado de $t$. Então, o caminho de $i$ para $j$ pode ter um peso arbitrariamente pequeno. Vamos denotar isso como -INF.

Implementação

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        for (int t = 0; t < n; ++t) {
            if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
                d[i][j] = - INF; 
        }
    }
}

Problemas