elmio




El camino más corto

          En la Teoría de grafos, el problema de los CAMINOS más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera quela suma de los pesos de las aristas que lo constituyen es mínima. 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 representan lasciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.
Formalmente, dado un grafo ponderado (que es un conjunto V de vértices, unconjunto E de aristas y una función de variable real ponderada f: E → R) y un elemento v ∈ V encuentra un camino P de v a v' ∈ V, tal que:

Es el mínimo entre todos los caminos que conectan v y v'.El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de la siguiente generalización:


El problema de los caminos más cortos desde unorigen 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 queencontrar 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 cortosentre 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.
Los algoritmos de los caminos más cortos se aplican paraencontrar direcciones de forma automática entre localizaciones físicas, tales como direcciones en mapas callejeros.

Si un algoritmo representa una máquina abstracta no determinista como un grafo, dondelos vértices describen estados, y las aristas posibles transiciones, el algoritmo de los caminos más cortos se usa para encontrar una secuencia óptima de opciones para llegar a un cierto estado final...