1. Inicio
  2. Pregunta y respuesta
  3. ¿Por qué no podemos aplicar el algoritmo de Dijkstra para un gráfico con pesos negativos?

¿Por qué no podemos aplicar el algoritmo de Dijkstra para un gráfico con pesos negativos?

2010-07-08 42 views

Respuesta

15

¿Qué significa encontrar la ruta menos costosa de A a B, si cada vez que viaja de C a D obtiene pagado?

Si hay un peso negativo entre dos nodos, la "ruta más corta" es hacer un ciclo hacia atrás y hacia adelante entre esos dos nodos para siempre. Cuanto más saltos, más "corta" es la ruta.

Esto no tiene nada que ver con el algoritmo, y todo tiene que ver con la imposibilidad de responder a esa pregunta.

Editar:

La afirmación anterior asume enlaces bidireccionales. Si no hay ciclos que tengan un peso negativo en general, no hay forma de dar vueltas para siempre, de que se les pague.

En tal caso, el algoritmo de Dijkstra todavía puede fallar:

considerar dos caminos:

  • un camino óptimo que bastidores hasta un costo de 100, antes de cruzar el borde final que tiene un -25 peso, dando un total de 75, y
  • un camino subóptimo que no tiene bordes negativamente ponderados con un costo total de 90.

algoritmo de Dijkstra se Inves Seleccione primero la ruta subóptima y se declarará terminada cuando la encuentre. Nunca seguirá el subpaso peor que la primera solución encontrada

Fuente

2010-07-08 03:17:55 Oddthinking

+3

Pero - Bellman-Ford funciona correctamente en presencia de bordes de peso negativos, siempre que no haya ciclos de peso negativos. Por lo tanto, hay algo sobre el algoritmo de Dijkstra que hace que falle, incluso si no se puede pasar entre dos nodos en un ciclo de peso negativo. – dsolimano

+3

@dsolimano: Sí. Considere dos caminos: (1) un camino óptimo que acumula un costo total de 100, antes de cruzar el borde final que tiene un peso de -25, dando un total de 75, y (2) un camino subóptimo que no tiene ponderación negativa bordes con un costo total de 90. El algoritmo de Dijkstra primero investigará el camino subóptimo y se declarará terminado cuando lo encuentre. Nunca seguirá el subpaso que sea peor que la primera solución encontrada. – Oddthinking

+1

@Oddthinking: Entonces, conoce la respuesta real (sí, tiene algo que ver con el algoritmo), por lo que debe promocionarla desde el comentario al texto de respuesta. –

2

Imagine que tiene un gráfico dirigido con un ciclo dirigido, y la "distancia" total alrededor de eso tiene un peso negativo. Si en su camino desde el vértice de inicio al final puede pasar por ese ciclo dirigido, puede simplemente dar vueltas y vueltas al ciclo dirigido un número arbitrario de veces.

Y eso significa que puede hacer que su camino a través del gráfico tenga una distancia infinitamente negativa (o efectivamente).

Sin embargo, mientras no haya ciclos dirigidos alrededor de su gráfico, podría salirse con la suya utilizando el Algoritmo de Dijkstra sin que explote nada.

Dicho todo esto, si tiene un gráfico con pesos negativos, puede usar el algoritmo Belman-Ford. Debido a la generalidad de este algoritmo, sin embargo, es un poco más lento. El algoritmo de Bellman-Ford toma O (V · E), donde el Dijkstra toma el tiempo O (E + VlogV)

Fuente

2012-04-19 02:52:59 theJollySin

4

Le daré un contraejemplo. Considere siguiente gráfico

http://img853.imageshack.us/img853/7318/3fk8.png

Supongamos que se inició en el vértice A y quieres camino más corto a D.el algoritmo de Dijkstra haría siguientes pasos:

  1. Marcos A que visitó y añadir vértices B y C que hacer cola
  2. Fetch desde el vértice cola con la distancia mínima. Es B
  3. Marcos B que visitó y añadir vértice D que hacer cola.
  4. Recuperar de la cola. No es el vértice D.
  5. Marcar como visitado D

Dijkstra dice más corto camino desde A a D tiene una longitud de 2, pero es obvio que no es cierto.

Fuente

2013-11-07 22:27:46 tomas789

Cuestiones relacionadas

 Cuestiones relacionadas