problema del camino mas corto



Contenido



PROBLEMA DE LA RUTA MAS CORTA
RESUMEN
Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o máscorta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto a otro. Se aplica mucho para problemas deredes de comunicaciones.
INTRODUCCION
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 elementov ∈ 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 entredos 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 atodos 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érticedestino, 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 cortosentre cada par de vértices (v , v') en el grafo.
ANTECEDENTES
Es difícil rastrear la historia del problema del camino más corto. Uno se puede imaginar que, incluso en las sociedades muy primitivas(aún la de los animales), es esencial encontrar rutas cortas (como por ejemplo para la comida). Comparado con otros problemas de optimización combinatoria —árbol de recubrimiento mínimo, asignación ytransporte— la investigación matemática en el problema del camino más corto comenzó relativamente tarde. Esto pudo haberse debido al hecho que el problema es elemental y más o menos fácil. lo que...