Encontrar un ciclo negativo en el grafo
Se da un grafo dirigido ponderado con vértices y aristas. Encontrar cualquier ciclo de peso negativo en él, si existe tal ciclo.
En otra formulación del problema hay que encontrar todos los pares de vértices entre los cuales hay un camino de peso arbitrariamente pequeño.
Es conveniente usar algoritmos distintos para resolver estas dos variantes del problema, así que discutiremos ambas aquí.
Usando el algoritmo de Bellman-Ford
El algoritmo de Bellman-Ford permite comprobar si existe un ciclo de peso negativo en el grafo y, si existe, encontrar uno de esos ciclos.
Los detalles del algoritmo se describen en el artículo sobre el algoritmo de Bellman-Ford. Aquí solo describiremos su aplicación a este problema.
La implementación estándar de Bellman-Ford busca un ciclo negativo alcanzable desde algún vértice de partida ; sin embargo, el algoritmo se puede modificar para buscar simplemente cualquier ciclo negativo en el grafo. Para esto hay que poner todas las distancias a cero y no a infinito — como si buscáramos el camino más corto desde todos los vértices simultáneamente; la validez de la detección de un ciclo negativo no se ve afectada.
Hacemos iteraciones del algoritmo de Bellman-Ford. Si no hubo cambios en la última iteración, no hay ciclo de peso negativo en el grafo. En caso contrario, tomamos un vértice cuya distancia haya cambiado, y desde él vamos por sus ancestros hasta encontrar un ciclo. Este ciclo será el ciclo de peso negativo deseado.
Implementación
struct Edge {
int a, b, cost;
};
int n;
vector<Edge> edges;
const int INF = 1000000000;
void solve() {
vector<int> d(n, 0);
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] = max(-INF, d[e.a] + e.cost);
p[e.b] = e.a;
x = e.b;
}
}
}
if (x == -1) {
cout << "No negative cycle found.";
} 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 << "Negative cycle: ";
for (int v : cycle)
cout << v << ' ';
cout << endl;
}
}Usando el algoritmo de Floyd-Warshall
El algoritmo de Floyd-Warshall permite resolver la segunda variante del problema: encontrar todos los pares de vértices que no tienen un camino más corto entre ellos (es decir, existe un camino de peso arbitrariamente pequeño).
De nuevo, los detalles se pueden encontrar en el artículo de Floyd-Warshall, y aquí solo describimos su aplicación.
Ejecutamos el algoritmo de Floyd-Warshall sobre el grafo.
Inicialmente para cada .
Pero después de ejecutar el algoritmo será menor que si existe un camino de longitud negativa de a .
Podemos usar esto para encontrar también todos los pares de vértices que no tienen un camino más corto entre ellos.
Iteramos sobre todos los pares de vértices y para cada par comprobamos si tienen un camino más corto entre ellos.
Para esto, probamos todas las posibilidades de un vértice intermedio .
no tiene un camino más corto si uno de los vértices intermedios tiene (es decir, forma parte de un ciclo de peso negativo), es alcanzable desde y es alcanzable desde .
Entonces el camino de a puede tener peso arbitrariamente pequeño.
Denotaremos esto con -INF.
Implementación
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;
}
}
}