Diferencia entre revisiones de «Usuario:Humberto0601ad jc/Felo»
| Línea 21: | Línea 21: | ||
'''Inicialización.''' | '''Inicialización.''' | ||
*Sea V un conjunto de vértices de un grafo. | *Sea V un conjunto de vértices de un grafo. | ||
| − | *Sea C una matriz de costos de las aristas del grafo, donde en | + | *Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v. |
| − | C[u,v] se almacena el costo de la arista entre u y v. | + | * Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo. |
| − | Sea S un conjunto que contendrá los vértices para los cuales ya | + | * Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v. |
| − | se tiene determinado el camino mínimo. | + | * Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido. |
| − | Sea D un arreglo unidimensional tal que D[v] es el costo del | + | * Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices. |
| − | camino mínimo del vértice origen al vértice v. | + | '''Paso 1.''' S ← {vinicial} //Inicialmente S contendrá el vértice //origen |
| − | Sea P un arreglo unidimensional tal que P[v] es el vértice | + | '''Paso 2.''' Para cada v∈V, v ≠ vinicial, hacer |
| − | predecesor de v en el camino mínimo que se tiene construido. | + | 2.1. D[v] ← C[vinicial, v] //Inicialmente el costo del //camino mínimo de vinicial a v es lo contenido en //la matriz de costos |
| − | Sea vinicial el vértice origen. Recordar que el Algoritmo | + | 2.2. P[v] ← vinicial //Inicialmente, el //predecesor de v en el camino mínimo construido //hasta el momento es vinicial |
| − | Dijkstra determina los caminos mínimos que existen partiendo de un | + | '''Paso 3.''' Mientras (V – S ≠ ∅) hacer //Mientras existan vértices para //los cuales no se ha determinado el //camino mínimo |
| − | vértice origen al resto de los vértices | + | 3.1. Elegir un vértice w∈(V-S) tal que D[w] sea el mínimo. |
| − | Paso 1. S ← {vinicial} //Inicialmente S contendrá el vértice | + | 3.2. S ← S ∪ {w} //Se agrega w al conjunto S, pues ya se //tiene el camino mínimo hacia w |
| − | //origen | + | 3.3. Para cada v∈(V-S) hacer |
| − | Paso 2. Para cada v∈V, v ≠ vinicial, hacer | + | 3.3.1. D[v] ← min(D[v],D[w]+C[w,v]) //Se escoge, entre |
| − | 2.1. D[v] ← C[vinicial, v] //Inicialmente el costo del | + | //el camino mínimo hacia v que se tiene //hasta el momento, y el camino hacia v //pasando por w mediante su camino mínimo, //el de menor costo. |
| − | //camino mínimo de vinicial a v es lo contenido en | + | 3.3.2. Si min(D[v],D[w]+C[w,v]) = D[w]+C[w,v] entonces P[v] ← w //Si se escoge ir por w entonces //el predecesor de v por el momento es w |
| − | //la matriz de costos | + | '''Paso 4. Fin ''' |
| − | 2.2. P[v] ← vinicial //Inicialmente, el | + | == te == |
| − | //predecesor de v en el camino mínimo construido | + | |
| − | //hasta el momento es vinicial | + | == rt == |
| − | Paso 3. Mientras (V – S ≠ ∅) hacer //Mientras existan vértices para | ||
| − | //los cuales no se ha determinado el | ||
| − | //camino mínimo | ||
| − | 3.1. Elegir un vértice w∈(V-S) tal que D[w] sea el mínimo. | ||
| − | 3.2. S ← S ∪ {w} //Se agrega w al conjunto S, pues ya se | ||
| − | //tiene el camino mínimo hacia w | ||
| − | 3.3. Para cada v∈(V-S) hacer | ||
| − | 3.3.1. D[v] ← min(D[v],D[w]+C[w,v]) //Se escoge, entre | ||
| − | //el camino mínimo hacia v que se tiene | ||
| − | //hasta el momento, y el camino hacia v | ||
| − | //pasando por w mediante su camino mínimo, | ||
| − | //el de menor costo. | ||
| − | 3.3.2. Si min(D[v],D[w]+C[w,v]) = D[w]+C[w,v] entonces | ||
| − | P[v] ← w //Si se escoge ir por w entonces | ||
| − | //el predecesor de v por el momento es w | ||
| − | Paso 4. Fin | ||
Revisión del 12:26 1 abr 2011
| ||||||
En múltiples aplicaciones donde se aplican los grafos, es necesario conocer el camino de menor costo entre dos vértices dados:
- Distribución de productos a una red de establecimientos comerciales.
- Distribución de correos postales.
- Sea G = (V, A) un grafo dirigido ponderado.
El problema del camino más corto de un vértice a otro consiste en determinar el camino de menor costo, desde un vértice u a otro vértice v. El costo de un camino es la suma de los costos (pesos) de los arcos que lo conforman.
Características del algoritmo
- Es un algoritmo greddy.
- Trabaja por etapas, y toma en cada etapa la mejor solución sin considerar consecuencias futuras.
- El óptimo encontrado en una etapa puede modificarse posteriormente si surge una solución mejor.
Pasos del algoritmo
Algoritmo 24.1: Algoritmo de Dijkstra. Inicialización.
- Sea V un conjunto de vértices de un grafo.
- Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.
- Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.
- Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.
- Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.
- Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.
Paso 1. S ← {vinicial} //Inicialmente S contendrá el vértice //origen Paso 2. Para cada v∈V, v ≠ vinicial, hacer
2.1. D[v] ← C[vinicial, v] //Inicialmente el costo del //camino mínimo de vinicial a v es lo contenido en //la matriz de costos
2.2. P[v] ← vinicial //Inicialmente, el //predecesor de v en el camino mínimo construido //hasta el momento es vinicial
Paso 3. Mientras (V – S ≠ ∅) hacer //Mientras existan vértices para //los cuales no se ha determinado el //camino mínimo
3.1. Elegir un vértice w∈(V-S) tal que D[w] sea el mínimo.
3.2. S ← S ∪ {w} //Se agrega w al conjunto S, pues ya se //tiene el camino mínimo hacia w
3.3. Para cada v∈(V-S) hacer
3.3.1. D[v] ← min(D[v],D[w]+C[w,v]) //Se escoge, entre
//el camino mínimo hacia v que se tiene //hasta el momento, y el camino hacia v //pasando por w mediante su camino mínimo, //el de menor costo.
3.3.2. Si min(D[v],D[w]+C[w,v]) = D[w]+C[w,v] entonces P[v] ← w //Si se escoge ir por w entonces //el predecesor de v por el momento es w
Paso 4. Fin
