Para el gráfico $G$ , vértices $s,t$ encontrar el camino más corto entre $s$ y $t$ por peso entre todos los caminos más cortos por aristas

Question

Dado el grafo dirigido $G=(V,E)$ dos vértices y una función de pesos $w: E \to R$ . Además sabemos que no hay ciclos negativos en $G$ . Necesito encontrar un algoritmo lineal que encuentre entre los caminos más cortos por aristas de $s$ a $t$ el camino más corto por peso.

Puedo encontrar el gráfico de todos los caminos más cortos desde $s$ a $t$ por dos BFS (para $s$ y de $t$ en $G^T$ - una versión de BFS que no se deshace de las aristas de los niveles posteriores), pero entonces ¿cómo encuentro en tiempo lineal el camino más corto por peso? Para eso tengo que usar Bellman-Ford, ¿no?

Muchas gracias.

Answer 1

Todos los caminos más cortos por aristas tienen la misma longitud, por lo que si se suma $w$ a cada arista no cambiará el camino más corto por peso. Elija un tamaño lo suficientemente grande $w$ para que cada arista sea positiva, y luego ejecutar el algoritmo de Dijkstra. (Pero esto no sería del todo lineal, ya que el algoritmo de Dijkstra se ejecuta en $O(\lvert E\rvert + \lvert V\rvert\ {\rm log}\ \lvert V\rvert)$ ).

Answer 2

¿No es este un trabajo para el algoritmo Floyd-Warshall

En informática, el algoritmo de Floyd-Warshall (también conocido como algoritmo de Floyd, algoritmo de Roy-Warshall, algoritmo de Roy-Floyd o algoritmo WFI) es un algoritmo de análisis de grafos para encontrar los caminos más cortos en un grafo ponderado (con pesos de aristas positivos o negativos) y también para encontrar el cierre transitivo de una relación R. Una sola ejecución del algoritmo encontrará las longitudes (pesos sumados) de los caminos más cortos entre todos los pares de vértices, aunque no devuelve detalles de los propios caminos

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm