algorithm - example - minimum spanning tree

Bellman Ford y One Olympiad Questions?

Question

Tomé un examen de la Olimpiada hace tres días. Me encontré con una buena pregunta de la siguiente manera.

Sabemos que los algoritmos de bellman-ford verifican todos los bordes en cada paso, y para cada borde si,

d (v)> d (u) + w (u, v)

entonces d(v) se actualiza de manera que w(u,v) es el peso del borde (u, v) y d(u) es la longitud de la mejor ruta de detección para el vértice u . Si en un paso no tenemos no update for vertexes , los algoritmos terminate . al suponer este algoritmo, para encontrar la ruta más corta desde el vértice s en la gráfica G con n vértice después de que se completa la iteración de k < n , ¿cuál de las siguientes opciones es correcta?

1) el número de bordes en todas las rutas más cortas desde s es a lo sumo k-1

2) el peso de todos los caminos más cortos desde s es a lo sumo k-1

3) La gráfica no tiene ciclo negativo.

¿Quién puede discutir sobre estas opciones?

Answer 1

1 es incorrecto, porque si relajamos los arcos en el orden topológico de un árbol de ruta más corto, convertimos en una iteración, a pesar de que el árbol de ruta más corto puede ser arbitrariamente profundo.

s --> t --> u --> v

Relax s->t, t->u, u->v; shortest path from s->v is three hops,
but B--F has made two iterations.

Si hacemos la relajación simultáneamente (es decir, siempre usamos los valores de la ronda r-1 en la ronda r, incluso si la ronda r los ha actualizado), entonces 1 es realmente correcto, por inducción (la profundidad del árbol de la ruta más corta comienza en cero y crece a lo sumo uno en cada ronda que no es el último).

2 es incorrecto, porque ¿quién sabe cuáles son los pesos?

  100
s --> t

Relax s->t; weight is 100, but B--F has made two iterations.

3 es correcto, ya que por un argumento de promediación, al menos un arco de un ciclo negativo no estaría relacionado. Sea v1, ..., vn un ciclo. Como los arcos están relajados, tenemos d(vi) + len(vi->vi+1) - d(vi+1) >= 0 . Sume las desigualdades de todos los términos i y el telescopio los términos d para simplificarlos a sum_i len(vi->vi+1) >= 0 , que dice que el ciclo no es negativo.

Answer 2

Creo que la opción 3 es incorrecta porque para saber si hay un ciclo de peso negativo, el algoritmo de Bellman Ford debe ejecutarse n veces. Primero n-1 veces para calcular la ruta más corta y luego una vez más para verificar si hay alguna mejora en las distancias si hay mejoras, esto significa que hay un ciclo de peso negativo.