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.^[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.

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 imes V imes ldots imes 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 ightarrow 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 ightarrow {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:

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]​

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(V⁴).

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.

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.