dijstra

El algoritmo de Dijkstra, también conocido como
algoritmo de caminos mínimos, sirve para determinar el
camino más corto dado un vértice o nodo inicial al resto
de los vértices de un grafo con pesoen cada arista
(distancia entre nodos).

Grafo con peso en las
aristas
Nodo
s
2

2
3

5
3

3

1

1

2

3
2

3
4

Peso en las aristas o
Distancia entre nodos

6

13

7

2

1) Para comenzar a
buscar el camino más
corto entre nodos, se
identifica el primer
nodo y se deja fijo. Se
le asigna el valor de la
distancia y de dónde
procede.

[3,1]2) Se busca la distancia
que hay entre los
nodos que están
unidos a 1.
3) Se suma la
distancia que hay
entre los nodos y la
que ya está
“guardada”.
4) Se busca cuál es
la distancia menorguardada en los
nodos y se deja fijo
este. (nodo con
menor distancia).

2

2
3

[0,-]
Distancia, Procedencia

3

3

1

1

5

2

3
2

3

4
[3,1]

6

1

3

7

21) Para comenzar a
buscar el camino más
corto entre nodos, se
identifica el primer
nodo y se deja fijo. Se
le asigna el valor de la
distancia y de dónde
procede.
2) Se busca la distancia
quehay entre los
nodos que están
unidos a 1.
3) Se suma la
distancia que hay
entre los nodos y la
que ya está
“guardada”.
4) Se busca cuál es
la distancia menor
guardada en los
nodos y sedeja fijo
este. (nodo con
menor distancia).

5) Se realiza lo
mismo que en
el paso 2) y
luego se
procede al
paso 3).
6) Se vuelve a
buscar cuál es
la menor
distancia
guardada en
los nodosy se
vuelve a dejar
fijo.

[3,1]
2

2

[5,2]

3

Distancia, Procedencia

3

3

1

1
[0,-]

5

2

3
2

3

4
[3,1]

[4,2]

6

1

3

7

2

1) Paracomenzar a
buscar el camino más
corto entre nodos, se
identifica el primer
nodo y se deja fijo. Se
le asigna el valor de la
distancia y de dónde
procede.
2) Se busca la distancia
que hay entre los...