Problema del camino más corto
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.
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.
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
se dice que es de longitud
Dada una función de variable real ponderada
Cuando cada arista en el grafo tiene un peso unitario o
El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de las siguientes generalizaciones: La distancia geodésica o simplemente distancia entre dos vértices es la longitud del camino más corto o geodésica entre ellos.
Si dos vértices no son accesibles a través de un camino, entonces la distancia entre ellos es infinita.
[1] Los algoritmos más importantes para resolver este problema son: Otros algoritmos y evaluaciones asociadas pueden se encontradas en el artículo de Cherkassky et al.
[2] 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] La siguiente tabla es tomada del Schrijver (2004).
[5] 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).
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.
Otras aplicaciones incluyen la investigación de operaciones, instalaciones y facilidad de diseño, robótica, transporte y el diseño VLSI.
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.
