Implementation (Part 2)
Lección 6 de 9 del curso Algoritmo de Bellman-Ford - Algoritmos de grafos de Coddy.
Ahora repite la pasada hasta que las distancias sean definitivas.
Desafío
IntermedioAhora el algoritmo completo: repite el paso de relajación hasta que las distancias se estabilicen.
Escribe una función llamada bellmanFord que reciba n, el arreglo plano edges (triples, dirigidos, posiblemente negativos) y un source, y devuelva la distancia más corta desde source a cada vértice. Usa -1 para los vértices inalcanzables. Asume que no hay ciclos negativos.
Relaja todas las aristas n - 1 veces.
Pruébalo tú mismo
#include <stdlib.h>
int* bellmanFord(int n, int* edges, int edges_size, int source, int* returnSize) {
// Escribe el código aquí
*returnSize = 0;
return edges;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Bellman-Ford - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity