Problematica¶
BFS permite encontrar el camino más corto desde un vértice fuente \(s\) a los demás en número de aristas, es decir en grafos que no son ponderados o cuyos pesos son iguales.
Por lo tanto, la métrica el número de aristas no es la mejor para el caso de los caminos más cortos
Recordar¶
El algoritmo relax
- Colocar todo v.d en \(\infty\) y v.s = 0, \(v.\pi = NIL\) inicialmente ningún nodo tiene padre
- \(\forall (u,v) \in E\) Si \(v.d < u.d + w(u,v)\)
- \(v.d = u.d + w(u,v)\)
- \(v.\pi = u\)