Problema del camino más corto

Ejemplo de Grafo Ponderado

En la teoría de grafos, el problema del camino más corto es el problema que consiste en encontrar un camino entre dos vértices o nodos, de tal manera que la suma de los pesos de las aristas que lo constituyen sea mínima. Al camino más corto entre dos vértices también se le conoce como geodésica.^[1]​

Este problema no necesariamente tiene una única solución.^[1]​ Además, tiene diversas aplicaciones. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representarían las ciudades y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

Definiciones

El problema del camino más corto puede ser definido para grafos no dirigidos o dirigidos. La siguiente es una definición para grafos no dirigidos, en el caso de grafos dirigidos la definición de camino requiere que los vértices adyacentes estén conectados por una apropiada arista dirigida.

Dos vértices son adyacentes cuando poseen una arista común. Un camino en un grafo no dirigido es una secuencia de vértices ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V}$ tal que todo vértice ${\displaystyle v_{i}}$ es adyacente con el vértice ${\displaystyle v_{i+1}}$. Un camino ${\displaystyle P}$ se dice que es de longitud ${\displaystyle n-1}$ si va desde ${\displaystyle v_{1}}$ hasta ${\displaystyle v_{n}}$.

Sea ${\displaystyle e_{i,j}}$ la arista incidente con los vértices ${\displaystyle v_{i}}$ y ${\displaystyle v_{j}}$. Dada una función de variable real ponderada ${\displaystyle f:E\rightarrow \mathbb {R} }$ y un grafo no dirigido ${\displaystyle G}$, el camino más corto desde ${\displaystyle v}$ hasta ${\displaystyle v'}$ es el camino ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$ (donde ${\displaystyle v_{1}=v}$ y ${\displaystyle v_{n}=v'}$) sobre todos los posibles ${\displaystyle n}$ que minimiza la suma ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$ Cuando cada arista en el grafo tiene un peso unitario o ${\displaystyle f:E\rightarrow \{1\}}$, hallar el camino más corto es equivalente a encontrar el camino con menor número de aristas.

El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de las siguientes generalizaciones:

• El problema de los caminos más cortos desde un origen, en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.
• El problema de los caminos más cortos con un destino, en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.
• El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

La distancia geodésica o simplemente distancia entre dos vértices es la longitud del camino más corto o geodésica entre ellos. La distancia entre dos vértices ${\displaystyle i}$ y ${\displaystyle j}$ se puede denotar como ${\displaystyle d(i,j)}$; en tal caso, note que ${\displaystyle d(i,j)=d(j,i)}$. Si dos vértices no son accesibles a través de un camino, entonces la distancia entre ellos es infinita.^[1]​

Algoritmos

Los algoritmos más importantes para resolver este problema son:

• Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos desde un único vértice origen hasta todos los otros vértices del grafo.
• Algoritmo de Bellman - Ford, resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa.
• Algoritmo de Búsqueda A*, resuelve el problema de los caminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda.
• Algoritmo de Floyd - Warshall, resuelve el problema de los caminos más cortos entre todos los vértices.
• Algoritmo de Johnson, resuelve el problema de los caminos más cortos entre todos los vértices y puede ser más rápido que el de Floyd-Warshall en grafos de baja densidad.
• Algoritmo de Viterbi, resuelve el problema del camino estocástico más corto con un peso probabilístico adicional en cada vértice.

Anexo: Ejemplo de Algoritmo de Dijkstra

Anexo: Ejemplo de Algoritmo de Bellman - Ford

Otros algoritmos y evaluaciones asociadas pueden se encontradas en el artículo de Cherkassky et al.^[2]​

Algoritmos para caminos más cortos desde un origen

Grafos no dirigidos

Ponderación	Complejidad Temporal	Autor
ℝ+	O(E + V log V)	Dijkstra, 1959
ℕ	O(E)	Thorup[3]​

Grafos dirigidos no ponderados

Algoritmo	Complejidad Temporal	Autor
Búsqueda en anchura	O(E + V)	E. F. Moore y C. Y. Lee de manera independiente.

Grafos acíclicos dirigidos

Un algoritmo usando ordenación topológica puede resolver el problema del camino más corto desde un origen en tiempo lineal, Θ(E + V), en DAG ponderados.^[4]​

Grafos dirigidos con ponderación no negativa

La siguiente tabla es tomada del Schrijver (2004).^[5]​

Algoritmo	Complejidad Temporal	Autor
	O(V^2EL)	Ford, 1956
Algoritmo de Bellman-Ford	O(VE)	Bellman, 1958,Moore, 1959
	O(V^2 log V)	Dantzig, 1958,Dantzig, 1960, Minty (cf.Pollack y Wiebenson, 1960),Whiting y Hillier, 1960
Algoritmo de Dijkstra con lista	O(V^2)	Leyzorek et al., 1957,Dijkstra, 1959
Algoritmo de Dijkstra con Montículo binario modificado	O((E + V) log V)
. . .	. . .	. . .
Algoritmo de Dijkstra con Montículo de Fibonacci	O(E + V log V)	Fredman y Tarjan, 1984,Fredman y Tarjan, 1987
	O(E log log L)	Johnson, 1982,Karlsson y Poblete, 1983
Algoritmo de Gabow	O(E logE/V L)	Gabow, 1983b,Gabow, 1985b
	O(E + V√log L)	Ahuja et al., 1990

Grafos dirigidos con ponderaciones arbitrarias

Algoritmo	Complejidad Temporal	Autor
Algoritmo de Bellman-Ford	O(EV)	Bellman, 1958,Moore, 1959

Algoritmos para caminos más cortos entre todos los pares de vértices

El problema del camino más corto entre todos los pares de vértices encuentra los caminos que sean más cortos entre todas las parejas de vértices v, v' en el grafo. El problema para grafos dirigidos no ponderados fue introducido por Shimbel (1953), quien observó que podría ser resuelto por una serie lineal de multiplicaciones matriciales que toma un tiempo total de O(V⁴).

Grafos no dirigidos

Ponderación	Complejidad Temporal	Algoritmo
ℝ+	O(V^3)	Algoritmo de Floyd-Warshall
ℝ+	O(EV log α(E,V))	Pettie-Ramachandran[6]​
ℕ	O(EV)	Thorup[3]​

Grafos dirigidos

Weights	Time complexity	Algorithm
ℝ (sin ciclos negativos)	O(V^3)	Algoritmo de Floyd-Warshall
ℝ (sin ciclos negativos)	O(EV + V^2 log V)	Johnson-Dijkstra
ℝ (sin ciclos negativos)	O(EV + V^2 log log V)	Johnson-Pettie[7]​
ℕ	O(EV + V^2 log log V)	Hagerup[8]​

Aplicaciones

Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre lugares físicos, como las rutas de conducción en sitios de mapas web como MapQuest o Google Maps. Para estas aplicaciones están disponibles rápidos algoritmos especializados.^[9]​

Si un algoritmo representa una máquina abstracta no determinista como un grafo, donde los vértices describen estados, y las aristas posibles transiciones, el algoritmo del camino más cortos puede ser usado para encontrar una secuencia óptima de decisiones para llegar a un cierto estado final o para establecer límites más bajos en el tiempo necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un puzle como el Cubo de Rubik y cada arista dirigida corresponde a un simple movimiento o giro, los algoritmos del camino más corto se pueden usar para encontrar la solución que utiliza el menor número posible de movimientos.

En el argot de las telecomunicaciones, a este algoritmo es también conocido como el problema del mínimo retraso, y con frecuencia va ligado con el problema del camino más ancho. Por ejemplo, el algoritmo podría buscar el camino más corto entre los más anchos, o el camino más ancho entre los más cortos.

Una aplicación más coloquial es la teoría de los "Seis grados de separación", a partir de la cual se intenta encontrar el camino más corto entre dos personas cualesquiera.

Otras aplicaciones incluyen la investigación de operaciones, instalaciones y facilidad de diseño, robótica, transporte y el diseño VLSI.

Problemas relacionados

En la geometría computacional, el problema del camino euclidiano más corto, en el cual dados un conjunto de obstáculos poliédricos en un espacio euclídeo y dos puntos, trata de encontrar el camino más corto entre los puntos tal que no se interseca con ninguno de los obstáculos.

El problema de viajante de comercio, es el problema que trata de encontrar el camino más corto que pasa sólo una vez por cada vértice y regresa al comienzo. A diferencia del problema del camino más corto, el cual puede ser resuelto en un tiempo polinomial en grafos sin ciclos negativos, este problema es NP-completo, y como tal, no tiene una resolución eficiente (ver Clases de complejidad P y NP). El problema de encontrar el camino más largo también es NP-completo.

El problema del viajero canadiense y el problema del camino estocástico más corto son generalizaciones donde el grafo no es completamente conocido por el viajero, cambia con el tiempo, o donde los recorridos son probabilisticos.

Véase también

• Búsqueda de ruta
• Problema del viajante
• IEEE 802.1aq
• Red de flujo
• Línea geodésica
• Curvas en sección de la Tierra

Referencias

1. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
2. Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). «Shortest paths algorithms: theory and experimental evaluation». Mathematical Programming. Ser. A 73 (2): 129-174. MR 1392160. doi:10.1016/0025-5610(95)00021-6. .
3. Thorup, Mikkel (1999). «Undirected single-source shortest paths with positive integer weights in linear time». Journal of the ACM (JACM) 46 (3): 362-394. Consultado el 28 de noviembre de 2014. 
4. Papamanthou, Charalampos (2004). Depth First Search & Directed Acyclic Graphs. pp. 12-14. Consultado el 2 de mayo de 2015. 
5. Schrijver, Alexander (2004). Combinatorial Optimization — Polyhedra and Efficiency. Algorithms and Combinatorics 24. Springer. ISBN 3-540-20456-3.  Aquí: vol.A, sec.7.5b, p.103
6. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. 2002.  pp.267–276
7. Theoretical Computer Science 312. 2004.  pp.47–74
8. Proceedings of the 27th International Colloquium on Automata, Languages and Programming. 2000.  pp.61–72
9. Sanders, Peter (23 de marzo de 2009). Fast route planning. Google Tech Talk. .

Bibliografía

• Bellman, Richard (1958). «On a routing problem». Quarterly of Applied Mathematics 16: 87-90. MR 0102435. 
• Dijkstra, E. W. (1959). «A note on two problems in connexion with graphs». Numerische Mathematik 1: 269-271. doi:10.1007/BF01386390. 
• Cormen, Thomas H. «Single-Source Shortest Paths and All-Pairs Shortest Paths». Introduction to Algorithms (2 edición). MIT Press. pp. 580-642. 
• Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338-346. ISBN 0-8186-0591-X. doi:10.1109/SFCS.1984.715934. Archivado desde el original el 11 de octubre de 2012. Consultado el 6 de mayo de 2015. 
• Fredman, Michael Lawrence; Tarjan, Robert E. (1987). «Fibonacci heaps and their uses in improved network optimization algorithms». Journal of the Association for Computing Machinery 34 (3): 596-615. doi:10.1145/28869.28874. 
• Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology. 
• Moore, E. F. (1959). «The shortest path through a maze». Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press. pp. 285-292. 
• Shimbel, Alfonso (1953). «Structural parameters of communication networks». Bulletin of Mathematical Biophysics 15 (4): 501-507. doi:10.1007/BF02476438. 
• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

• Datos: Q1058754