Embed Size (px)
Citation preview
Algoritmo de Dijkstra
Algoritmo de Dijkstra.
Uno de los algoritmos mas usados para la busqueda de caminos de peso mınimo esel de Dijkstra, que proporciona los pesos mınimos desde un vertice dado al resto delos vertices.
Algoritmo de Dijkstra
Algoritmo de Dijkstra.
Uno de los algoritmos mas usados para la busqueda de caminos de peso mınimo esel de Dijkstra, que proporciona los pesos mınimos desde un vertice dado al resto delos vertices.
Sea un grafo o digrafo pesado, con V = v1, v2, . . . , vn su conjunto de verticesy Ω = (ωij)n×n su matriz de pesos, y sea vp el vertice inicial.
Algoritmo de Dijkstra
Algoritmo de Dijkstra.
Uno de los algoritmos mas usados para la busqueda de caminos de peso mınimo esel de Dijkstra, que proporciona los pesos mınimos desde un vertice dado al resto delos vertices.
Sea un grafo o digrafo pesado, con V = v1, v2, . . . , vn su conjunto de verticesy Ω = (ωij)n×n su matriz de pesos, y sea vp el vertice inicial.
Dijkstra construye, en cada paso, un camino mınimo desde vp a otro vertice yse detiene cuando ha construido uno para cada vertice (o no puede construir mas).Para ello se usan
Algoritmo de Dijkstra
Algoritmo de Dijkstra.
Uno de los algoritmos mas usados para la busqueda de caminos de peso mınimo esel de Dijkstra, que proporciona los pesos mınimos desde un vertice dado al resto delos vertices.
Sea un grafo o digrafo pesado, con V = v1, v2, . . . , vn su conjunto de verticesy Ω = (ωij)n×n su matriz de pesos, y sea vp el vertice inicial.
Dijkstra construye, en cada paso, un camino mınimo desde vp a otro vertice yse detiene cuando ha construido uno para cada vertice (o no puede construir mas).Para ello se usan
? una lista o conjunto: L , que contendra los vertices para los que hemos cons-truimos un camino mınimo
Algoritmo de Dijkstra
Algoritmo de Dijkstra.
Uno de los algoritmos mas usados para la busqueda de caminos de peso mınimo esel de Dijkstra, que proporciona los pesos mınimos desde un vertice dado al resto delos vertices.
Sea un grafo o digrafo pesado, con V = v1, v2, . . . , vn su conjunto de verticesy Ω = (ωij)n×n su matriz de pesos, y sea vp el vertice inicial.
Dijkstra construye, en cada paso, un camino mınimo desde vp a otro vertice yse detiene cuando ha construido uno para cada vertice (o no puede construir mas).Para ello se usan
? una lista o conjunto: L , que contendra los vertices para los que hemos cons-truimos un camino mınimo
? y un vector de pesos: D , que contendra al final los pesos mınimos.
Algoritmo de Dijkstra
Algoritmo de Dijkstra.
Uno de los algoritmos mas usados para la busqueda de caminos de peso mınimo esel de Dijkstra, que proporciona los pesos mınimos desde un vertice dado al resto delos vertices.
Sea un grafo o digrafo pesado, con V = v1, v2, . . . , vn su conjunto de verticesy Ω = (ωij)n×n su matriz de pesos, y sea vp el vertice inicial.
Dijkstra construye, en cada paso, un camino mınimo desde vp a otro vertice yse detiene cuando ha construido uno para cada vertice (o no puede construir mas).Para ello se usan
? una lista o conjunto: L , que contendra los vertices para los que hemos cons-truimos un camino mınimo
? y un vector de pesos: D , que contendra al final los pesos mınimos.
Inicialmente L = vp y D = Ω(p, : ) , la p -esima fila de la matriz de pesos (lacorrespondiente al vertice inicial).
1
Algoritmo de Dijkstra
Algoritmo de Dijkstra
inicio: Ω; vp ; L = vp; D = Ω(p, : )mientras sea V− L 6= ∅
tomar vk ∈ V− L con D(k) mınimohacer L ∪ vkpara cada vj de V-Lsi D(j) > D(k) + Ω(k, j)hacer D(j) = D(k) + Ω(k, j)
fin
fin
fin
El vector D final contiene los pesos mınimos desde el vertice inicial a los demasvertices –si alguno de los pesos finales es ∞, no hay camino desde el vertice inicial–.
Algoritmo de Dijkstra
Algoritmo de Dijkstra
inicio: Ω; vp ; L = vp; D = Ω(p, : )mientras sea V− L 6= ∅
tomar vk ∈ V− L con D(k) mınimohacer L ∪ vkpara cada vj de V-Lsi D(j) > D(k) + Ω(k, j)hacer D(j) = D(k) + Ω(k, j)
fin
fin
fin
El vector D final contiene los pesos mınimos desde el vertice inicial a los demasvertices –si alguno de los pesos finales es ∞, no hay camino desde el vertice inicial–.
Para la aplicacion del algoritmo con lapiz y papel, se coloca el vector D inicial comola primera fila de una tabla, de manera que en las filas sucesivas se van colocandolos nuevos valores de D tras cada minoracion.
2
Algoritmo de Dijkstra
Aplicacion Sea G ,
yy
y
y
y
y
yv1
v2
v3
v4
v5
v6
v7
9
3
3
7
1
1
7
5
2
8
9
4
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
yy
y
y
y
y
yv1
v2
v3
v4
v5
v6
v7
9
3
3
7
1
1
7
5
2
8
9
4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
yy
y
y
y
y
yv1
v2
v3
v4
v5
v6
v7
9
3
3
7
1
1
7
5
2
8
9
4v1 y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
0 3 9 ∞ ∞ ∞ ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
v2
[ 9 ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ 3 ]
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
0 3 9 ∞ ∞ ∞ ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
v2
[ 9 ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ 3 ]
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
0 3 9 ∞ ∞ ∞ ∞
mınD(2), D(3), D(4), D(5), D(6), D(7)
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 9 ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 9 ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 9 ]
2
¿D(3) < D(2) + Ω(2, 3)?
9 < 3 + 2
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ ∞ ]
[ ∞ ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ ∞ ]7
¿D(4) < D(2) + Ω(2, 4)?
∞ < 3 + 7
[ ∞ ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ ∞ ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]1
[ ∞ ]¿D(5) < D(2) + Ω(2, 5)?
∞ < 3 + 1
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ 4 ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ 4 ]
[ ∞ ]
∞
¿D(6) < D(2) + Ω(2, 6)?
∞ < 3 + ∞[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ 4 ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10 4 ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ 4 ]
[ ∞ ]
[ ∞ ]
∞
¿D(7) < D(2) + Ω(2, 7)?
∞ < 3 + ∞v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10 4 ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ 4 ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10 4 ∞ ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]
[ 4 ]
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞0 3 5 10 4 ∞ ∞
mınD(3), D(4), D(5), D(6), D(7)
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]1
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]1
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]1
[ ∞ ]
[ ∞ ]1 ¿D(3) < D(5) + Ω(5, 3)?
5 < 4 + 1v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]1
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 10 ]1
[ ∞ ]
[ ∞ ]
5
¿D(4) < D(5) + Ω(5, 4)?
10 < 4 + 5v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 9 ]1
[ ∞ ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 9 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 9 ]1
[ ∞ ]
[ ∞ ]
9¿D(6) < D(5) + Ω(5, 6)?
∞ < 4 + 9v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 9 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 9 4 13
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 9 ]1
[ 13 ]
[ ∞ ]
∞¿D(7) < D(5) + Ω(5, 7)?
∞ < 4 + ∞v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 9 4 13
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 9 4 13 ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
[ 5 ]
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞
0 3 5 9 4 13 ∞
mınD(3), D(4), D(6), D(7)
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]
7¿D(4) < D(3) + Ω(3, 4)?
9 < 5 + 7v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 9 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]
∞
¿D(6) < D(3) + Ω(3, 6)?
13 < 5 + ∞v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 9 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 9 4 13
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]
∞ ¿D(7) < D(3) + Ω(3, 7)?
∞ < 5 + ∞v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 9 4 13
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 9 4 13 ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
[ 9 ]1
[ 13 ]
[ ∞ ]v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞
0 3 5 9 4 13 ∞
mınD(4), D(6), D(7)
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 13 ]
[ ∞ ]
5
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 13 ]
[ ∞ ]
5
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
0 3 5 9 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 13 ]
[ ∞ ]
5
2
¿D(6) < D(4) + Ω(4, 6)?
13 < 9 + 2v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
0 3 5 9 4
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 11 ]
[ ∞ ]
5
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
0 3 5 9 4 11
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 11 ]
[ ∞ ]
5
8
¿D(7) < D(4) + Ω(4, 7)?
∞ < 9 + 8v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
0 3 5 9 4 11
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 11 ]
[ 17 ]
5
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
0 3 5 9 4 11 17
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 11 ]
[ 17 ]
5
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞
0 3 5 9 4 11 17
mınD(6), D(7)
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 17 ]
5
2
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞L ∪ 6 0 3 5 9 4 11 17
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 17 ]
5
2
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞L ∪ 6 0 3 5 9 4 11 17
0 3 5 9 4 11
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 17 ]
5
2
4
¿D(7) < D(6) + Ω(6, 7)?
17 < 11 + 4v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞L ∪ 6 0 3 5 9 4 11 17
0 3 5 9 4 11
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
3
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
[ 15 ]
5
2
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞L ∪ 6 0 3 5 9 4 11 17
0 3 5 9 4 11 15
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
3
Algoritmo de Dijkstra
Aplicacion Sea G , y Ω su matriz de pesos
v1
3
v2
2
1
5
2
4
v5v3
v4v6
v7
yy
yy
y y
y
L = 1 D(1) D(2) D(3) D(4) D(5) D(6) D(7)
L ∪ 2 0 3 9 ∞ ∞ ∞ ∞L ∪ 5 0 3 5 10 4 ∞ ∞L ∪ 3 0 3 5 9 4 13 ∞L ∪ 4 0 3 5 9 4 13 ∞L ∪ 6 0 3 5 9 4 11 17
L ∪ 7 0 3 5 9 4 11 15
Ω v1 v2 v3 v4 v5 v6 v7
v1 0 3 9 ∞ ∞ ∞ ∞v2 3 0 2 7 1 ∞ ∞v3 9 2 0 7 1 ∞ ∞v4 ∞ 7 7 0 5 2 8v5 ∞ 1 1 5 0 9 ∞v6 ∞ ∞ ∞ 2 9 0 4v7 ∞ ∞ ∞ 8 ∞ 4 0
3
