Camino Mínimo Algoritmo de DIJKSTRA

Formalmente, dado un grafo ponderado (que es un conjunto V de vértices, un conjunto A de aristas

y una variable real que permite ponderar cada arista A ) se trata de resolver:

• El problema de los caminos más cortos desde un origen en el cual tenemos

que encontrar los caminos más cortos de un vértice origen v a todos los
demás vértices del grafo.

El método de dijkstra usa una técnica basada en el principio de que para que un camino sea
óptimo, todos los caminos que contiene también deben ser óptimos- entre todos los vértices
adyacentes. Este principio se basa además en el principio de optimalidad de Bellman :

“Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve

un problema también debe ser óptima respecto al subproblema que resuelve.” ( ver documento:
programación dinámica - grafos)

Este método utiliza la siguiente nomenclatura asociada a cada nodo (vértice)

distancia acumulada; nodo precede

se estructura en los siguientes pasos :

ejemplo :
figura 1

∞; ∞;
5
C F
1
0;A 2 3 ∞;
2
A D H
3 1
∞; 4
B 1
5
∞; E
2
G
∞;
∞;
El algoritmo parte de un vértice origen que está determinado, a partir de ese vértices evaluaremos
sus adyacentes,
Paso 1 : marcamos todos los vértices con el símbolo ∞ como distancia acumulada indicando como no
utilizados, excepto el vértice origen al que le asignamos a distancia acumulada el valor 0 pues es el
erigen. En la figura 1 se encuentran en cada nodo la representación
en el vértice origen es 0; A y los restantes son ∞;
Paso 2: El algoritmo parte de un vértice origen que está determinado, a partir de ese vértices
evaluaremos sus adyacentes, así podemos evaluar el vértice C y el vértice B y calculamos la
distancia y la procedencia resultando entonces
1; A
0; A C
A 1
3 B
3; A
paso 3: De los vértices evaluados ( que hasta el momento son estos) debemos seleccionar el de
distancia menor , en este caso resulta el vértice C ; entonces este nodo ya queda marcado y así nos
resulta la figura 2

1; A ∞;
5
C F
1
0;A 2 3 ∞;
2
A D H
3 1
∞; 4
B 1
5
3; E
2
A G
∞;
∞;
paso 4: a partir de ese vértice evaluaremos todos sus adyacentes, calculamos
distancia acumulada; nodo precede

Es decir repetimos el procedimiento desde el paso 2: evaluamos los adyacentes al vértice C

 1; A 5 F
0; A 1 C 6; C
A 2 D
3 B 3; C
3; A
Repetimos paso 3 , de los vértices evaluados NO marcados ( es decir el B ; D; f ) debemos
seleccionar el de distancia menor, en este caso hay dos con un acumulado =3. Es indistinto cual
seleccionamos para marcar. Decidimos el D. Resulta el figura 3

Figura
3

1; A 6;C
5
C F
1
0;A 2 3
2
A D H
3 1
3;C 4
B 1
5
3; A E
2
G
∞;
∞;

Repetimos el paso 2, como queda marcado el vértice D, evaluamos los adyacentes entre los vértices
no evaluados F; E; B cuyos acumulados son 5; 7 ; 3
repetimos paso 3 seleccionamos el de menor valor de l distancia acumulada, es el que corresponde
al vértice B,
resula figura 4
 5;D
1; A 6;C
5
C F
1
0;A 2 3 ∞;
2
A D H
3 1
3;C 4
B 1
5
3; A E
2
G
4; D 7;D
∞;
Observaión importante : se recalcula el vértice F resultando una distancia acumulada menor por eso
se tacha lo calculado anteriormente, en el caso del vértice B el nuevo valor calculado resulta mayor
por lo tanto este último es el que se descarta persistiendo el anterior.
Repetimos los paso pasos 2 y 3 hasta marcar todos los vértices como quedan indicados en los grafos
siguientes
figura 5
5;D
1; A 6;C
5
C F
1
0;A 2 3 ∞;
2
A D H
3 1
3;C 4
B 1
5
3; A E
2
G
4; D 7;D
8; B
Figura 6

5;D
1; A 6;C
5
C F
1
0;A 2 3 8;F
2
A D H
3 1
3;C 4
B 1
5
3; A E
2
G
4; 7;D
D
8; B
Figura
7
5;D
1; A 6;C
5 8 ;E
C F
1
0;A 2 3 8 ;F
2
A D H
3 1
3;C 4
B 1
5
3; A E
2
G
4; D 7;D
8; B
9; E
 5;D
1; A 6;C
5 8 ;E
C F
1
0;A 2 3 8;
2
F
A D H
3 1
3;C 4
B 1
5
3; A E
2
G
4; D 7;D
8; B
9; E

De esta manera queda el camino más corto a cualquiera de los vértices , en particular al los más
lejanos que son G y H cuyos mínimos resultan iguales a 8.
Recorriendo de atrás hacia adelante por los vértices precedentes resulta desde H :
H – F – D – C – A es decir el camino es A – c – F – D – H = 8
Análogamente el camino mínimo de A hasta G : G – B – A = 8, es decir el camino es A – B – G