Algoritmo De Dijkstra

Grafos
Camino Coste Mínimo

Algoritmo de Dijkstra

Aplicaciones
► Encaminamiento

de paquetes por los routers ► Aplicaciones para Sistemas de información geográficos: ► Reconocimiento delenguaje hablado
Otras Aplicaciones
► Enrutamiento

de aviones y tráfico aéreo. ► Tratamiento de imágenes médicas.

Introducción
► Supongamos

un grafo G, con pesos positivos y un nodo origenv.
algoritmo trabaja con dos conjuntos de nodos:  Escogidos: S. Nodos para los cuales se conoce ya el camino mínimo desde el origen.  Candidatos: T. Nodos pendientes de calcular el camino mínimo,aunque conocemos los caminos mínimos desde el origen pasando por nodos de S.

► El

IDEA
►

Camino especial: camino desde el origen hasta un nodo, que pasa sólo por nodos escogidos, S.

1

26

4

T
9

S
3 8 7 5

• Idea: En cada paso, coger el nodo de T con menor distancia al origen. Añadirlo a S. • Recalcular los caminos mínimos de los demás candidatos, pudiendo pasar por elnodo cogido.

Pequeño Ejemplo
b 7
Vértice Inicial

 3  2

1 8

c  4 5
Costos

s

0

a

5



d

Asignamos ∞ a todos los vértices menos al de partida

v D[v] Ant[v]Color[v]

s 0 null White

a  Null White

b  Null White

c  Null White

d  Null White

Cola Prioridad D[v]

a 2

b 7

Paso 1
b 7 7 3 2 a 2 2 1 ~ 8 4 5 ~ c
Automáticamente los nodosadyacentes son rotulados con el coste de sus arcos

Tenemos 2 nodos Adyacentes a 0, el 7 y el 2. Al comparar sus costos nos damos cuenta que ir a 2 tiene un menor coste (2)

s 0

d

5

NodoEscogido

v D[v] Ant[v] Color[v]

s 0 null Black

a 2 S Black

b 7 S White

c  Null White

d  Null White

Cola Prioridad D[v]

b 5

c 10

d 7

Paso 2
b
7 5 1

c 10
4
Y cque tenia rotulado ∞ ahora se rotula 10, que es el costo desde a -> c (8) + el rotulo de a (2). Igualmente el nodo d.

Entre las posibilidades del nodo “a” tenemos el costo 8 hacia “c”, s 5 hacia...