Introducción
El problema de camino mínimo en grafos, nace al intentar ir de un punto minimizando el costo, ya sea distancia recorrida, tiempo empleado, entre otros factores.
Consiste así el problema en encontrar un camino entre dos vértices(o nodos) de tal manera que la suma de los pesos de las aristas que constituyen el camino sea mínima.
Tipos de problemas de camino mínimo en grafos:
- Problema de camino mínimo desde un origen: en el cual tenemos que encontrar los caminos más cortos desde un vértice V a todos los demás vértices del grafo.
- Problema de camino más corto con un destino: se puede considerar el inverso del problema anterior, un vértice D es el destino y hay que encontrar el camino más corto desde todos los demás.
- Problema de camino mínimo entre todos los pares de vértices :como su nombre indica es considerar alguno de los dos problemas anteriores pero para cada vértice del grafo.
Nuestro problema consistirá pues en encontrar un camino entre dos o más nodos, tal que el peso de las aristas que lo constituyen sea mínimo.
Previo al comienzo de cualquier estudio, es conveniente mirar si ya existen recursos que puedan ser útiles con el tema en cuestión para ello veamos un breve resumen de los algoritmos relacionados con caminos mínimos en grafos previo a su desarrollo:
- Algoritmo de Dijkstra: es un algoritmo para la determinación del camino más corto, dado un vértice origen, hacia el resto de los vértices en un grafo que tiene pesos en cada arista.
- Algoritmo de Bellman - Ford: resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa.
- Algoritmo de Johnson}: permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo para encontrar el camino más corto.
Planteado ya nuestro problema inicial es natural hacerse al siguiente pregunta ¿Para que sirve nuestro problema?
Algunos de los multitudinarios y distintos ejemplos que pueden ser usados para reflejar la importancia del problema son de los más comunes en nuestra vida cotidiana; por ejemplo, encontrar direcciones de forma automática entre lugares físicos usando las rutas de conducción en sitios de mapas web tales como MapQuest o Google Maps. Por otro lado en el sector de las comunicaciones este problema es frecuentado como el problema del mínimo retraso, y con frecuencia va ligado con el problema del camino mas "ancho"(en cuanto a ancho de banda se refiere). Prácticamente podemos encontrar tantos problemas asociado a los caminos mínimos en grafos como le sea posible a nuestra imaginación.