La pregunta dada es una modificación del algoritmo de Dijkstra. Primero calcule las longitudes de camino más cortas de todos los vértices desde los vértices de origen utilizando el algoritmo de Dijkstra de origen único.
Deje que dist [u] [0] sea la distancia más corta desde s hasta el vértice u.
Ahora, cuando agrega un borde ab de dos vías en el gráfico, la ruta más corta de s a t podría cambiar. Si b estuviera en la ruta más corta de s a t, entonces
- ¿Cuál es una manera sencilla de encontrar big-O, big-Theta y big-Omega para una función determinada?
- ¿Cuáles son algunos algoritmos para el comercio de acciones automatizado?
- En algoritmos, ¿cuál es el límite superior e inferior?
- ¿Cuál es la mejor manera de aprender a escribir algoritmos?
- ¿Cómo calcula Google la distancia entre dos lugares en Google Maps?
d [t] [0] = d [b] [0] + distancia más corta (b, t)
Al agregar el borde ab
Diga d1 = min (d [b] [0], d [a] [0] + longitud de borde (a, b)) + distancia más corta (b, t)
Del mismo modo, a también puede estar en el camino más corto de sa t
Diga d2 = min (d [a] [0], d [b] [0] + longitud de borde (b, a)) + distancia más corta (a, t)
Si el mínimo entre d1 y d2 es menor que d [t] [0], actualice el valor de respuesta y verifique lo anterior para todos los bordes ab
Y para la distancia más corta (b, t), no es necesario volver a aplicar el Algoritmo de Dijkstra (dará TLE incluso si lo hace). Así que precalcule estos valores aplicando el Algoritmo de Dijkstra en el gráfico invertido y con el vértice inicial como t.
