Implementation (Part 1)
Leçon 5 sur 9 du cours Algorithme de Bellman-Ford - Algorithmes de graphes de Coddy.
Tout d'abord, une seule passe de relaxation sur toutes les arêtes.
Défi
MoyenBellman-Ford est simplement une opération répétée : une passe de relaxation sur toutes les arêtes. Construisons une seule passe.
Écrivez une fonction nommée relaxAll qui prend n, le tableau plat edges (triplets, orientés, potentiellement négatifs), et une source. Commencez avec dist[source] = 0 et tous les autres à l'infini, puis relâchez chaque arête une fois (dans l'ordre donné) et renvoyez les distances résultantes, en utilisant -1 pour les sommets encore non atteints.
Comme il ne s'agit que d'une seule passe, les sommets accessibles uniquement via plusieurs arêtes peuvent encore être -1. C'est attendu.
Essayez vous-même
#include <stdlib.h>
int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
// Écrivez le code ici
*returnSize = 0;
return edges;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Algorithme de Bellman-Ford - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity