4.3.3. Problemas de caminos mínimos.
Definición: Dado un grafo ponderado G= (V, A) (dirigido o no) y un camino w1, w2, ..., wq en G, el costo del camino será la suma de los costos asociados a las aristas (w1, w2), ..., (wq-1, wq).
Si el grafo es no ponderado, normalmente el costo se asocia con la longitud del camino.
Problema de los caminos más cortos por un origen:
Encontrar los caminos más cortos entre un nodo origen dado y todos los demás nodos.
Supongamos un grafo ponderado G (con pesos ? 0) y un nodo origen v.
El algoritmo trabaja con dos conjuntos:
- S: conjunto de nodos escogidos, para los cuales se conoce el camino de distancia mínima al origen.
- C: conjunto de nodos candidatos, pendientes de calcular el camino mínimo. Conocemos los caminos mínimos al origen pasando por nodos de S.
En cada paso coger del conjunto de candidatos el nodo con distancia mínima al origen. Recalcular los caminos de los demás candidatos pasando por el nodo cogido.