5.3.1 El camino más corto

 En la teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) en un gráfico de tal manera que la suma de los pesos de sus bordes constituyentes se reduce al mínimo. 

Esto es análogo al problema de encontrar el camino más corto entre dos intersecciones en un mapa de carreteras: vértices del gráfico corresponden a las intersecciones y los bordes corresponden a los segmentos de carretera, cada uno ponderado por la longitud de su segmento de carretera. 

Los algoritmos más importantes para la solución de este problema son: 

El algoritmo de Dijkstra: Resuelve las cortas de origen único problemas de ruta. 

Algoritmo de Bellman-Ford: Resuelve el problema de una sola fuente, si borde pesos pueden ser negativos. 

Un algoritmo de búsqueda *: Resuelve para el par de ruta más corta única utilizando la heurística para tratar de acelerar la búsqueda. 

Algoritmo de Floyd-Warshall: Resuelve todos los pares caminos más cortos.

Algoritmo de Johnson: Resuelve todos los pares de trayectorias más cortas, y puede ser más rápido que Floyd-Warshall en grafos dispersos.

Ahora bien, podemos emplear el algoritmo de Dijkstra para éstos casos, los pasos o procedimientos a seguir para éste algoritmo son los siguientes : Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi
4. Si la distancia desde x hasta va guardada en D es mayor que la distancia desde x hasta a, sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada.
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenándolos valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.