Implementation (Part 1)
Lección 5 de 9 del curso Algoritmo de Bellman-Ford - Algoritmos de grafos de Coddy.
Primero, una única pasada de relajación sobre todas las aristas.
Desafío
IntermedioBellman-Ford es simplemente una operación repetida: una pasada de relajación sobre todas las aristas. Vamos a construir una sola pasada.
Escribe una función llamada relaxAll que reciba n, el arreglo plano edges (triples, dirigidos, posiblemente negativos) y un source. Comienza con dist[source] = 0 y todos los demás en el infinito, luego relaja cada arista una vez (en el orden dado) y devuelve las distancias resultantes, usando -1 para los vértices que aún no han sido alcanzados.
Debido a que es solo una pasada, los vértices alcanzables solo a través de varias aristas pueden seguir siendo -1. Eso es lo esperado.
Pruébalo tú mismo
#include <stdlib.h>
int* relaxAll(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