Herramientas de usuario

Herramientas del sitio


algoritmos-oia:grafos:bellman-ford

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Próxima revisión
Revisión previa
algoritmos-oia:grafos:bellman-ford [2017/12/03 20:06]
sebach creado
algoritmos-oia:grafos:bellman-ford [2017/12/26 19:12] (actual)
sebach ↷ Page moved from algoritmos-oia:bellman-ford to algoritmos-oia:grafos:bellman-ford
Línea 13: Línea 13:
 El algoritmo consiste en hacer varias veces lo siguiente: recorrer todas las aristas. Si la arista $(u,v)$ de longitud $L$ es tal que la distancia que teníamos guardada desde **source** hasta el nodo $u$ más la longitud de la arista $L$, es menor a la distancia que teníamos guardada hasta el nodo $v$, actualizamos la información de la distancia hasta el nodo $v$ como la suma mencionada. El algoritmo consiste en hacer varias veces lo siguiente: recorrer todas las aristas. Si la arista $(u,v)$ de longitud $L$ es tal que la distancia que teníamos guardada desde **source** hasta el nodo $u$ más la longitud de la arista $L$, es menor a la distancia que teníamos guardada hasta el nodo $v$, actualizamos la información de la distancia hasta el nodo $v$ como la suma mencionada.
  
-Cuántas veces tenemos que recorrer las aristas? La idea fuerte del algoritmo es que alcanza con recorrerlas una vez por cada nodo, es decir si el grafo tiene $V$ nodos, ​hacemos eso $V$ veces. Se ve entonces que la **complejidad del algoritmo** es $\large O(V.E)$ donde $V$ es la cantidad de vértices y $E$ la de aristas.+Cuántas veces tenemos que recorrer las aristas? La idea fuerte del algoritmo es que si el grafo tiene $V$ nodos, ​alcanza con recorrer las aristas ​$V-1$ veces. Se ve entonces que la **complejidad del algoritmo** es $\large O(V.E)$ donde $V$ es la cantidad de vértices y $E$ la de aristas. 
 +La demostración de esta idea puede verse en wikipedia ([[https://​en.wikipedia.org/​wiki/​Bellman%E2%80%93Ford_algorithm#​Proof_of_correctness|Bellman-Ford]]),​ prueba por inducción que después de recorrer las aristas $i$ veces, en cada nodo hay guardada la mejor distancia desde el nodo **source** con a lo sumo $i$ aristas (al principio con $0$ aristas, la única información es que hasta el mismo nodo **source** la menor distancia vale $0$). Como, si no hay ciclos negativos, no vamos a pasar más de una vez por ningún vertice, en un camino hay a lo sumo $V-1$ aristas.
  
-Ahora, hay un caso excepcional que puede ocurrir que es que hay un ciclo de suma negativa. Si por ejemplo tuvieramos las aristas $(u, v), (v, w), (w, u)$ de pesos $10, -5, -12$ respectivamente,​ al llegar al nodo $u$ con cualquier distancia nos conviene ir al nodo $v$, luego al $w$ y volver al $u$, habiendo reducido la distancia anterior. Y nos conviene hacer eso indefinidamente.+Ahora, hay un caso excepcional que puede ocurrir que es que haya un ciclo de suma negativa. Si por ejemplo tuvieramos las aristas $(u, v), (v, w), (w, u)$ de pesos $10, -5, -12$ respectivamente,​ al llegar al nodo $u$ con cualquier distancia nos conviene ir al nodo $v$, luego al $w$ y volver al $u$, habiendo reducido la distancia anterior. Y nos conviene hacer eso indefinidamente.
  
 Lo que afirma el algoritmo es que si luego de recorrer todas las aritas $V$ veces, hacemos esto una vez más y encontramos una arista $(u, v)$ que hace que la suma de la distancia actual hasta $u$ más la longitud de la arista nos achique la distancia obtenida hasta el nodo $v$, entonces hay un ciclo negativo, y el problema no tiene sentido, ya que no hay una distancia mínimo hasta los nodos que estén en el ciclo negativo pues podemos achicarla cuanto queramos. Lo que afirma el algoritmo es que si luego de recorrer todas las aritas $V$ veces, hacemos esto una vez más y encontramos una arista $(u, v)$ que hace que la suma de la distancia actual hasta $u$ más la longitud de la arista nos achique la distancia obtenida hasta el nodo $v$, entonces hay un ciclo negativo, y el problema no tiene sentido, ya que no hay una distancia mínimo hasta los nodos que estén en el ciclo negativo pues podemos achicarla cuanto queramos.
 +
 +
 +Algo que podemos hacer para reconstruir caminos, que sirve en general en muchos algoritmos de grafos, es, al actualizar la distancia, guardar esa actualización en un vector "​antecesor",​ que significa que para llegar al nodo $v$ nos conviene llegar desde el $u$, por ejemplo.
 +
 +Y por último, algo que no mejora la eficiencia en el peor caso pero no es muy complejo de agregar, es la siguiente idea: si recorro todas las aristas, y no actualizo ninguna información,​ en el siguiente va a pasar exactamente lo mismo. Entonces si una vez no actualizé nada, puedo cortar el algoritmo aunque haya hecho el procedimiento menos de $V$ veces.
 +
 +=== Código ===
 +
 +<code cpp>
 +
 +#define forn(i,n) for(int i=0;​i<​(int)(n);​ i++)
 +
 +struct arista{
 + int u, v, longitud;
 +};
 +
 +vector<​int>​ bellmanFord(vector<​arista>​ grafo, int source, int cantidadNodos){
 + int INF=2e9;
 + vector<​int>​ distancia(cantidadNodos,​ INF);
 + vector<​int>​ antecesor(cantidadNodos,​ -1);
 + distancia[source]=0;​
 + forn(_, cantidadNodos-1){
 + bool modifico=false;​
 + forn(j, grafo.size()){
 + arista actual = grafo[j];
 + if( distancia[actual.u] + actual.longitud < distancia[actual.v] ){
 + distancia[actual.v] = distancia[actual.u] + actual.longitud;​
 + antecesor[actual.v]=actual.u;​
 + modifico=true;​
 + }
 + }
 + if(!modifico){
 + break;
 + }
 + }
 +
 + forn(j, grafo.size()){
 + arista actual = grafo[j];
 + if( distancia[actual.u] + actual.longitud < distancia[actual.v] ){
 + cout<<"​ERROR,​ CICLO NEGATIVO"<<​endl;​
 + }
 + }
 + return distancia;
 +}
 +
 +</​code>​
algoritmos-oia/grafos/bellman-ford.1512331568.txt.gz · Última modificación: 2017/12/03 20:06 por sebach