Dado un gráfico G conectado y no dirigido , un árbol de la ruta más corta con raíz en el vértice v es un árbol de expansión T de G , de modo que la distancia de la ruta desde la raíz v a cualquier otro vértice u en T es la distancia de la ruta más corta desde v hasta u en G .
En gráficos conectados donde las rutas más cortas están bien definidas (es decir, donde no hay ciclos de longitud negativa), podemos construir un árbol de ruta más corta usando el siguiente algoritmo:
- Calcule dist ( u ), la distancia de la ruta más corta desde la raíz v al vértice u en G utilizando el algoritmo de Dijkstra o el algoritmo de Bellman-Ford .
- Para todos los vértices no raíz u , podemos asignarle a u un vértice padre p u tal que p u esté conectado a u , y que dist ( p u ) + edge_dist ( p u , u ) = dist ( u ). En caso de que existan múltiples opciones para p u , elija p u para el que exista un camino más corto de v a p u con el menor número de aristas posible; esta regla de desempate es necesaria para evitar bucles cuando existen ciclos de longitud cero.
- Construya el árbol de la ruta más corta usando los bordes entre cada nodo y su padre.
El algoritmo anterior garantiza la existencia de árboles de ruta más corta. Al igual que los árboles de extensión mínima , los árboles de camino más corto en general no son únicos.
En los gráficos para los que todos los pesos de los bordes son iguales a uno, los árboles de la ruta más corta coinciden con los árboles de búsqueda de ancho primero .
En los gráficos que tienen ciclos negativos, el conjunto de rutas simples más cortas desde v hasta todos los demás vértices no necesariamente forman un árbol.
Ver también
Referencias
Cahn, Robert S. (1998). Diseño de redes de área amplia: conceptos y herramientas para la optimización . Redes. Morgan Kaufmann. ISBN 978-1558604582.