Loading AI tools
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 De Wikipedia, la enciclopedia libre
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 tal que todo vértice es adyacente con el vértice . Un camino se dice que es de longitud si va desde hasta .
Sea la arista incidente con los vértices y . Dada una función de variable real ponderada y un grafo no dirigido , el camino más corto desde hasta es el camino (donde y ) sobre todos los posibles que minimiza la suma Cuando cada arista en el grafo tiene un peso unitario o , 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 y se puede denotar como ; en tal caso, note que . 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]
Ponderación | Complejidad Temporal | Autor |
---|---|---|
ℝ+ | O(E + V log V) | Dijkstra, 1959 |
ℕ | O(E) | Thorup[3] |
Algoritmo | Complejidad Temporal | Autor |
---|---|---|
Búsqueda en anchura | O(E + V) | E. F. Moore y C. Y. Lee de manera independiente. |
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]
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 + V√log L) | Ahuja et al., 1990 |
Algoritmo | Complejidad Temporal | Autor |
---|---|---|
Algoritmo de Bellman-Ford | O(EV) | Bellman, 1958,Moore, 1959 |
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).
Ponderación | Complejidad Temporal | Algoritmo |
---|---|---|
ℝ+ | O(V3) | Algoritmo de Floyd-Warshall |
ℝ+ | O(EV log α(E,V)) | Pettie-Ramachandran[6] |
ℕ | O(EV) | Thorup[3] |
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[7] |
ℕ | O(EV + V2 log log V) | Hagerup[8] |
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.