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 es mínima. Un ejemplo de esto 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.

Definición

El problema del camino más corto puede ser definido para grafos no dirigidos, dirigidos o mixtos. 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 P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \ldots \times V tal que todo vértice v_i es adyacente con el vértice v_{i+1}. Un camino P se dice que es de longitud n si va desde v_1 hasta v_n.

Sea e_{i, j} la arista incidente con los vértices v_i y v_j. Dada una función de variable real ponderada f: E \rightarrow \mathbb{R} y un grafo no dirigido G, el camino más corto desde v hasta v' es el camino P = ( v_1, v_2, \ldots, v_n ) (donde v_1 = v y v_n = v') sobre todos los posibles n que minimiza la suma \sum_{i =1}^{n-1} f(e_{i, i+1}). Cuando cada arista en el grafo tiene un peso unitario o 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:

Algoritmos

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

Anexo: Ejemplo de Algoritmo de Bellman - Ford

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

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[2]

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.[3]

Grafos dirigidos con ponderación no negativa

La siguiente tabla es tomada del Schrijver (2004).[4]

Algoritmo Complejidad Temporal Autor
O(V2EL) Ford, 1956
Algoritmo de Bellman-Ford O(VE) Bellman, 1958, Moore, 1959
O(V2 log V) Dantzig, 1958, Dantzig, 1960, Minty (cf. Pollack y Wiebenson, 1960), Whiting y Hillier, 1960
Algoritmo de Dijkstra con lista O(V2) 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 + Vlog 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(V4).

Grafos no dirigidos

Ponderación Complejidad Temporal Algoritmo
+ O(V3) Algoritmo de Floyd-Warshall
+ O(EV log α(E,V)) Pettie-Ramachandran[5]
O(EV) Thorup[2]

Grafos dirigidos

Weights Time complexity Algorithm
ℝ (sin ciclos negativos) O(V3) Algoritmo de Floyd-Warshall
ℝ (sin ciclos negativos) O(EV + V2 log V) Johnson-Dijkstra
ℝ (sin ciclos negativos) O(EV + V2 log log V) Johnson-Pettie[6]
O(EV + V2 log log V) Hagerup[7]

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.[8]

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 puzzle 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

Referencias

  1. Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). «Shortest paths algorithms: theory and experimental evaluation». Mathematical Programming. Ser. A 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. MR 1392160..
  2. 1 2 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.
  3. Papamanthou, Charalampos (2004). Depth First Search & Directed Acyclic Graphs. pp. 12–14. Consultado el 2 de mayo de 2015.
  4. 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
  5. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. 2002. pp.267–276
  6. Theoretical Computer Science 312. 2004. pp.47–74
  7. Proceedings of the 27th International Colloquium on Automata, Languages and Programming. 2000. pp.61–72
  8. [Peter] Comprueba el valor del |enlaceautor= (ayuda) (23 de marzo de 2009). Fast route planning. Google Tech Talk..

Enlaces externos

This article is issued from Wikipedia - version of the Saturday, December 05, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.