Análisis y Diseño de Algoritmos II

“Caminos mínimos desde un

origen”
Claudia Pereira – Liliana Martinez
 Caminos mínimos desde un origen
Algoritmo de Dijkstra:

Dado un grafo rotulado G(V,A), encuentra el “camino mínimo” entre un

vértice origen y todos los restantes vértices de V.

Consideraciones:

✔ El costo del camino: suma de los costos de los arcos del camino

✔ Cada arco(u,v)/arista(u,v) posee un costo no negativo

 Algoritmo de Dijkstra: repaso

Dijkstra ( G( V , A) , origen ) {
// paso 1: Inicializa conjunto solución S
S = { origen };
// Inicializa distancias y predecesor
distancia [origen] = 0; predecesor[origen] = -1;
∀ v : v Є V y v ≠ origen {
distancia [v] = costo (origen,v);
predecesor[v] = origen;}
}
 Algoritmo de Dijkstra: repaso
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
}
} // end Dijkstra
 Algoritmo de Dijkstra: repaso

origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5

[ distancia al vértice origen / predecesor]

 Algoritmo de Dijkstra: repaso

[ 2 / 1]
origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5
[ 1 / 1]
[ distancia / predecesor]
 Algoritmo de Dijkstra: repaso

[ 2 / 1]
origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5
[ 1 / 1]
[ distancia / predecesor]
 Algoritmo de Dijkstra: repaso

[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ distancia / predecesor]
 Algoritmo de Dijkstra: repaso

[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ distancia / predecesor]
 Algoritmo de Dijkstra: repaso
[ 3 / 2]
[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ 5 / 2] [ distancia / predecesor]
 Algoritmo de Dijkstra: repaso
[ 3 / 2]
[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ 5 / 2] [ distancia / predecesor]
 Algoritmo de Dijkstra: repaso
[ 3 / 2]
[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6 [ 5 / 4]
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ 5 / 2] [ distancia / predecesor]
 Algoritmo de Dijkstra: repaso
[ 3 / 2]
[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6 [ 5 / 4]
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ 5 / 2] [ distancia / predecesor]
 Algoritmo de Dijkstra: repaso
[ 3 / 2]
[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6 [ 5 / 4]
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ 5 / 2] [ distancia / predecesor]
 Algoritmo de Dijkstra: repaso
[ 3 / 2]
[ 2 / 1] [ 5 / 3]
origen 1
2 4
2 2
4
1 4 6 [ 5 / 4]
3
1 1
3 5
5
[ 1 / 1] [ 6 / 3]
[ 5 / 2] [ distancia / predecesor]
 Algoritmo de Dijkstra: variantes

Ejercicio 1:

Dados un grafo G= (V, A), un vértice origen y un vértice destino,

modificar el algoritmo de Dijkstra para hallar el camino más corto

entre el origen y el destino.

Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9

Dijkstra ( G( V , A) , origen ) {
// paso 1: Inicializa conjunto solución S
S = { origen };
// Inicializa distancias y predecesor
distancia[origen]= 0; predecesor[origen]= -1;
∀ v : v Є V y v ≠ origen {
distancia [v] = costo (origen,v);
predecesor[v] = origen;}
}
Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9

Dijkstra ( G( V , A) , origen ) {
// paso 1: Inicializa conjunto solución S
S = { origen };
// Inicializa distancias y predecesor
distancia[origen]= 0; predecesor[origen]= -1;
∀ v : v Є V y v ≠ origen {
distancia [v] = costo (origen,v);
predecesor[v] = origen;}
}
Distancia Predecesor
Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} -
Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9

Dijkstra ( G( V , A) , origen ) {
// paso 1: Inicializa conjunto solución S
S = { origen };
// Inicializa distancias y predecesor
distancia[origen]= 0; predecesor[origen]= -1;
∀ v : v Є V y v ≠ origen {
distancia [v] = costo (origen,v);
predecesor[v] = origen;}
}
Distancia Predecesor
Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 -1
Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9

Dijkstra ( G( V , A) , origen ) {
// paso 1: Inicializa conjunto solución S
S = { origen };
// Inicializa distancias y predecesor
distancia[origen]= 0; predecesor[origen]= -1;
∀ v : v Є V y v ≠ origen {
distancia [v] = costo (origen,v);
predecesor[v] = origen;}
}
Distancia Predecesor
Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 -1
Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9

Dijkstra ( G( V , A) , origen ) {
// paso 1: Inicializa conjunto solución S
S = { origen };
// Inicializa distancias y predecesor
distancia[origen]= 0; predecesor[origen]= -1;
∀ v : v Є V y v ≠ origen {
distancia [v] = costo (origen,v);
predecesor[v] = origen;}
}
Distancia Predecesor
Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2
2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2
2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2 6 2
2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2 6 2
2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2 6 5 2 1
2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2 0 2 6 ∞ ∞ 9 5 ∞ ∞ -1 1 2 1 1 1 1 1 1
2
 Modificar el algoritmo de Dijkstra para hallar el camino de 1 a 9
// pasos 2-n: Calcula n-1 caminos mínimos
Mientras (V–S) ≠ Ø
{ // Elegir un vértice w ∈ V - S tal que D[w] sea mínimo
w = ExtraerMin(V - S) : distancia[w] sea mínima
// agrega w al conjunto solución S,
S = S U {w};
∀ v : v Є ady (w) y v Є (V–S)
//D[v]= min(D[v],D[w]+C[w,v])
Si distancia [v] > distancia [w] + costo (w,v) {
distancia [v]= distancia [w] + costo (w,v);
Predecesor[v] = w;
}
} Distancia Predecesor
} Iteración S w
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
Inicialización {1} - 0 2 ∞ ∞ ∞ 9 5 ∞ ∞ -1 1 1 1 1 1 1 1 1
1 { 1, 2 } 2 0 2 6 ∞ ∞ 9 5 ∞ ∞ -1 1 2 1 1 1 1 1 1
2 ?
Completar el seguimiento
 Algoritmo de Dijkstra: variantes

Ejercicio 2:

Dado un grafo G= (V, A), encontrar el camino más corto a un

vértice destino dado desde cada uno de los vértices.