Obteniendo un ciclo negativo usando Bellman Ford

20

Tengo que encontrar un ciclo negativo en un gráfico ponderado dirigido. Sé cómo funciona el algoritmo Bellman Ford, y que me dice si hay un ciclo negativo alcanzable. Pero no lo nombra explícitamente.

¿Cómo puedo obtener la ruta real del ciclo?v1,v2,vk,v1

Después de aplicar el algoritmo estándar, ya hicimos iteraciones y no debería ser posible ninguna mejora adicional. Si aún podemos reducir la distancia a un nodo, existe un ciclo negativo.n1

Mi idea es: dado que conocemos el borde que aún puede mejorar el camino y conocemos el predecesor de cada nodo, podemos rastrear nuestro camino desde ese borde hasta que lo encontremos nuevamente. Ahora deberíamos tener nuestro ciclo.

Lamentablemente, no encontré ningún documento que me diga si esto es correcto. Entonces, ¿realmente funciona así?

Editar: este ejemplo demuestra que mi idea es incorrecta. Dado el siguiente gráfico, ejecutamos Bellman-Ford desde el nodo .1

ingrese la descripción de la imagen aquí

Procesamos aristas en el orden . Después de n - 1 iteraciones obtenemos distancias de nodo: 1 : - 5 2 : - 30 3 : - 15a,b,c,dn1
1:5
2:30
3:15

y tabla padre:
tiene padre 3 2 tiene padre 3 3 tiene padre 213
23
32

n1aa

c,da

¿Cómo podemos resolver este problema?

Patrick Schmidt
fuente

Respuestas:

14

v1

s

Paresh
fuente
El enlace está roto.
human.js
Acabo de utilizar la idea del profesor Huang, pero no entiendo por qué agrega tanto un nuevo nodo fuente como un nuevo objetivo ( s'y t'). Me pareció que un nuevo nodo fuente, conectado a todos los vértices existentes por un borde de cualquier longitud, activaría todos los ciclos.
AbuNassar
0

Su ejemplo no contradice su idea. De hecho, has encontrado un ciclo negativo. Creo que la idea que ilustra su ejemplo es que el vértice de origen podría no ser un nodo en el ciclo negativo.

Espartano 117
fuente