Dado un gráfico y un vértice fuente src en el gráfico, encuentre las rutas más cortas desde src a todos los vértices en el gráfico dado. El gráfico puede contener bordes de peso negativos.
Algoritmo
Los siguientes son los pasos detallados.
- ¿Cuáles son los algoritmos hash más comunes además de MD5 y SHA?
- ¿Está bien inicializar una matriz que contiene fracciones en c ++?
- ¿Para qué se utiliza el algoritmo de fuerza bruta?
- ¿Cuál es la aplicación práctica de un gráfico no ponderado?
- ¿Cuál es mejor, búsqueda binaria o búsqueda lineal?
Entrada: Gráfico y una fuente de vértice src
Salida: distancia más corta a todos los vértices desde src . Si hay un ciclo de peso negativo, entonces no se calculan las distancias más cortas, se informa el ciclo de peso negativo.
1) Este paso inicializa las distancias desde la fuente a todos los vértices como infinitas y la distancia a la fuente como 0. Crea una matriz dist [] de tamaño | V | con todos los valores como infinitos excepto dist [src] donde src es el vértice fuente.
2) Este paso calcula las distancias más cortas. Haga lo siguiente | V | -1 veces donde | V | es el número de vértices en un gráfico dado.
… .. a) Haz lo siguiente para cada borde uv
……………… Si dist [v]> dist [u] + peso del borde uv, actualice dist [v]
………………… .dist [v] = dist [u] + peso del borde uv
3) Este paso informa si hay un ciclo de peso negativo en el gráfico. Haga lo siguiente para cada borde uv
…… Si dist [v]> dist [u] + peso del borde uv, entonces “El gráfico contiene un ciclo de peso negativo”
La idea del paso 3 es que el paso 2 garantiza distancias más cortas si el gráfico no contiene un ciclo de peso negativo. Si iteramos por todos los bordes una vez más y obtenemos una ruta más corta para cualquier vértice, entonces hay un ciclo de peso negativo
Algoritmo de Bellman – Ford http://codingeek.org/algorithms/…
