5.31 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 que la 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 las ciudades, 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, un conjunto 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 un origen 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 que encontrar 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 cortos entre 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.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf