CAMINO MAS CORTO: ALGORITMO DE BELLMAN-FORD
Enviado por Albert • 22 de Octubre de 2017 • 8.734 Palabras (35 Páginas) • 631 Visitas
...
1
2
3
4
5
6
7
//función de inicialización
void init(){
for( int i = 0 ; i
distancia[ i ] = INF; //inicializamos todas las distancias con valor infinito
previo[ i ] = -1; //inicializamos el previo del vértice i con -1
}
}
De acuerdo al vértice inicial que elijamos cambiara la distancia inicial, por ejemplo la ruta más corta partiendo del vértice 1 a todos los demás vértices. [pic 9]
Inicialmente la distancia de vértice 1 -> vértice 1 es 0 por estar en el mismo lugar.
1
distancia[ inicial ] = 0; //Este paso es importante, inicializamos la distancia del inicial como 0
Hasta este momento la tabla quedaría de la siguiente manera:
[pic 10]
Ahora según Bellman-Ford debemos realizar el paso de relajación |V| – 1 = 5 – 1 = 4 veces para cada arista:
1
2
3
for( int i = 1 ; i
…
}
Primera Iteración
Empezamos con las aristas que parten del vértice 1:
[pic 11]
Como podemos observar tenemos 2 aristas, la que une vértice 1 con vértice 2 y vértice 1 con vértice 4. Ello en código:
1
2
3
4
5
6
7
for( int actual = 1 ; actual
for( int j = 0 ; j
int adyacente = ady[ actual ][ j ].v; //id del vertice adyacente
int peso = ady[ actual ][ j ].w; //peso de la arista que une actual con adyacente ( actual , adyacente )
…
}
}
Las aristas de acuerdo al código serian de la forma e = (actual , adyacente , peso) donde actual es el vértice de donde partimos (en este caso sería 1) adyacente son los vértices que unen la arista e (en este caso serían los vértices 2 y 4) y peso son los pesos de cada arista (en este caso tendríamos 7 y 2).
Evaluamos primero para vértice 2:
[pic 12]
Vemos que la distancia actual desde el vértice inicial a 2 es ∞, verifiquemos el paso de relajación:
distancia[ 1 ] + 7 0 + 7 7
El paso de relajación es posible realizarlo entonces actualizamos la distancia en el vértice 2 quedando:
[pic 13][pic 14]
El paso de relajación se daría en la siguiente parte:
1
2
3
4
5
6
7
8
for( int actual = 1 ; actual
for( int j = 0 ; j
int adyacente = ady[ actual ][ j ].v; //id del vertice adyacente
int peso = ady[ actual ][ j ].w; //peso de la arista que une actual con adyacente ( actual , adyacente )
//Realizamos paso de relajacion para la arista actual
relajacion( actual , adyacente , peso );
}
}
Donde la función de relajación seria
1
2
3
4
5
6
7
8
9
//Paso de relajacion
void relajacion( int actual , int adyacente , int peso ){
//Si la distancia del origen al vertice actual + peso de su arista es menor a la distancia del origen al vertice adyacente
if( distancia[ actual ] + peso
distancia[ adyacente ] = distancia[ actual ] + peso; //relajamos el vertice actualizando la distancia
previo[ adyacente ] = actual; //a su vez actualizamos el vertice previo
Q.push( Node( adyacente , distancia[ adyacente ] ) ); //agregamos adyacente a la cola de prioridad
}
}
Ahora evaluamos al siguiente adyacente que es el vértice 4:
[pic 15]
De manera similar al anterior vemos que la distancia actual desde el vértice inicial a 4 es ∞, verifiquemos el paso de relajación:
...