Pregunta 1: Dada una gráfica ponderada dirigida. También se le proporciona la ruta más corta desde un vértice de origen ‘s’ hasta un vértice de destino ‘t’. Si el peso de cada borde aumenta en 10 unidades, ¿el camino más corto sigue siendo el mismo en el gráfico modificado?
El camino más corto puede cambiar. La razón es que puede haber un número diferente de aristas en diferentes caminos de s a t. Por ejemplo, deje que el camino más corto tenga un peso de 15 y tenga 5 aristas. Sea otro camino con 2 aristas y un peso total de 25. El peso del camino más corto aumenta en 5*10 y se convierte en 15 + 50. El peso del otro camino aumenta en 2*10 y se convierte en 25 + 20. Entonces, el la ruta más corta cambia a la otra ruta con un peso de 45.
Pregunta 2: Esto es similar a la pregunta anterior. ¿Cambia el camino más corto cuando los pesos de todos los bordes se multiplican por 10?
Si multiplicamos todos los pesos de los bordes por 10, el camino más corto no cambia. La razón es simple, los pesos de todos los caminos de s a t se multiplican por la misma cantidad. El número de aristas en un camino no importa. Es como cambiar la unidad de pesos.
Pregunta 3: dado un gráfico dirigido donde cada borde tiene peso como 1 o 2, encuentra el camino más corto desde un vértice de origen dado ‘s’ a un vértice de destino dado ‘t’. La complejidad de tiempo esperada es O(V+E).
Si aplicamos el algoritmo de camino más corto de Dijkstra , podemos obtener un camino más corto en tiempo O(E + VLogV). ¿Cómo hacerlo en tiempo O(V+E)? La idea es utilizar BFS . Una observación importante sobre BFS es que la ruta utilizada en BFS siempre tiene la menor cantidad de aristas entre dos vértices. Entonces, si todos los bordes tienen el mismo peso, podemos usar BFS para encontrar el camino más corto. Para este problema, podemos modificar el gráfico y dividir todos los bordes de peso 2 en dos bordes de peso 1 cada uno. En el gráfico modificado, podemos usar BFS para encontrar el camino más corto. ¿Cómo es este enfoque O(V+E)? En el peor de los casos, todos los bordes tienen un peso de 2 y necesitamos realizar operaciones O(E) para dividir todos los bordes, por lo que la complejidad del tiempo se convierte en O(E) + O(V+E), que es O(V+E).
Pregunta 4: Dado un gráfico ponderado acíclico dirigido, ¿cómo encontrar el camino más corto desde una fuente s hasta un destino t en un tiempo O(V+E)?
Ver: Ruta más corta en gráfico acíclico dirigido
Más preguntas Consulte los siguientes enlaces para obtener más preguntas.
https://www.geeksforgeeks.org/algorithms-gq/graph-shortest-paths-gq/
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA