Teoria de Grafos

UNIVERSIDAD DE COSTA RICA
ESCUELA DE CIENCIAS DE LA
COMPUTACION E INFORMATICA

CI-1204
Prof. Roxana Vargas

ESTRUCTURAS DISCRETAS APLICADAS II
Problema de la ruta más corta
Al etiquetar unaarista dirigida con el nombre de los nodos que une, siempre se pone
primero el nodo de donde viene y después el nodo al que va, esto es, una arista dirigida del
nodo A al nodo B debe etiquetarsecomo AB y NO como BA. Otra manera de etiquetarlo es la
siguiente: A → B.
Para ayudar a distinguir entre aristas dirigidas y no dirigidas, se hará referencia a las
aristas no dirigidas como ligaduras.Def: Un nodo de origen (fuente) tiene la propiedad de que su invariancia es cero.
Def: Un nodo destino (pozo) tiene la propiedad de que su exvariancia es cero.
El problema de la ruta más corta seocupa de encontrar la ruta más corta desde el
origen a un destino a través de una red conexa (grafo conexo y no dirigido), dada la distancia
no negativa asociada a las respectivas ramas (aristas) dela red. Aunque se han propuesto
varios procedimientos de solución (algoritmos) parecidos, la versión que aquí se describe es
tal vez la más corta y sencilla. La esencia de este procedimiento es elanálisis de toda la red
a partir del origen, al identificar sucesivamente la ruta más corta a cada uno de los nodos en
orden ascendente de sus distancias (más cortas) desde el origen, quedandoresuelto el
problema en el momento de llegar al nodo destino.

Algoritmo de la ruta más corta
Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este
paso se repetirápara n = 1,2, ... hasta que el n-ésimo nodo más cercano sea el nodo
destino.)
Datos para la n-ésima iteración: (n- l) nodos más cercanos al origen (encontrados en las
iteraciones previas), y tambiénsu ruta más corta y la distancia desde el origen. (Estos nodos
y el origen se llamarán nodos resueltos; el resto son nodos no resueltos.)
Candidatos para el n-ésimo nodo más cercano: cada nodo...