Corrección del algoritmo de Bellman-Ford, ¿podemos seguir mejor?

Question

Aprendí que el algoritmo Bellman-Ford tiene un tiempo de ejecución de O (| E | * | V |), en el que la E es el número de bordes y v el número de vértices.Supongamos que el gráfico no tiene ciclos ponderados negativos.

Mi primera pregunta es que ¿cómo demostramos que dentro de (| v | -1) iteraciones (cada iteración comprueba cada ventaja en e), actualiza la ruta más corta a cada nodo posible, dado un nodo de inicio en particular?¿Es posible que hemos iterado (| V | -1) veces, pero aún no terminamos con caminos más cortos a cada nodo?

Asumir la corrección del algoritmo, ¿podemos hacerlo realmente mejor que eso?Se me ocurre que no todos los bordes están ponderados negativamente en un gráfico en particular.El algoritmo Bellman-Ford parece caro, ya que cada iteración pasa a través de todos los bordes.

Answer 1

La ruta más larga posible de la fuente a cualquier vértice implicaría a lo sumo a la mayoría de todos los demás vértices en el gráfico. En otras palabras, no tendrá un camino que pase por el mismo verticio más de una vez, ya que eso necesariamente aumentaría los pesos (esto es cierto solo gracias al hecho de que no hay ciclos negativos). En cada iteración, usted actualizará el peso del camino más corto en el siguiente vértice en este camino, hasta después | V | -1 ITERACIONES Sus actualizaciones tendrían que llegar al final de ese camino. Después de eso, no habrá ningún vértice con valores no estrechos, ya que su actualización ha cubierto todas las rutas más cortas hasta esa longitud.

Esta complejidad es apretada (al menos para BF), piense en una larga línea de vértices conectados. Elija la más a la izquierda como la fuente: su proceso de actualización tendría que trabajar desde allí al otro lado una vez que el vértice a la vez. Ahora, puede argumentar que no tiene que revisar cada borde de esa manera, así que vamos a lanzar unos pocos bordes aleatorios con un peso muy grande (n> | v | * max-peso), no pueden ayudarlo, sino Su algoritmo no puede saber que seguro, por lo que si tiene que pasar por el proceso de actualización de los vértices con estos pesos (siguen siendo mejores que el infinito inicial).