En matemáticas y ciencias de la computación , un árbol de camino más corto con raíz en un vértice v de un grafo conexo no dirigido G es un árbol de expansión T de G , tal que la distancia del camino desde la raíz v hasta cualquier otro vértice u en T es la distancia del camino más corto desde v hasta u en G.
En gráficos conexos donde los caminos más cortos están bien definidos (es decir, donde no hay ciclos de longitud negativa), podemos construir un árbol de caminos más cortos utilizando el siguiente algoritmo:
El algoritmo anterior garantiza la existencia de árboles de ruta más corta. Al igual que los árboles de expansión mínima , los árboles de ruta más corta en general no son únicos.
En los gráficos en los que todos los pesos de los bordes son iguales, los árboles de ruta más corta coinciden con los árboles de búsqueda en amplitud .
En gráficos que tienen ciclos negativos, el conjunto de caminos simples más cortos desde v a todos los demás vértices no necesariamente forman un árbol.
Para gráficos conectados simples, se pueden usar árboles de ruta más corta [1] para sugerir una relación no lineal entre dos medidas de centralidad de red , cercanía y grado . Al suponer que las ramas de los árboles de ruta más corta son estadísticamente similares para cualquier nodo raíz en una red, se puede demostrar que el tamaño de las ramas depende solo del número de ramas conectadas al vértice raíz, es decir, al grado del nodo raíz. De esto se deduce que la inversa de la cercanía, una escala de longitud asociada con cada vértice, varía aproximadamente linealmente con el logaritmo del grado. La relación no es exacta pero captura una correlación entre cercanía y grado en un gran número de redes construidas a partir de datos reales [1] y este éxito sugiere que los árboles de ruta más corta pueden ser una aproximación útil en el análisis de redes.
Cahn, Robert S. (1998). Diseño de redes de área amplia: conceptos y herramientas para la optimización . Redes. Morgan Kaufmann. ISBN 978-1558604582.