Implementation (Part 2)

Leçon 6 sur 9 du cours Algorithme de Bellman-Ford - Algorithmes de graphes de Coddy.

Maintenant, répétez le passage jusqu'à ce que les distances soient définitives.

Défi

Moyen

Maintenant, l'algorithme complet : répétez la passe de relaxation jusqu'à ce que les distances se stabilisent.

Écrivez une fonction nommée bellmanFord qui prend n, le tableau plat edges (triplets, dirigés, potentiellement négatifs), et une source, et renvoie la distance la plus courte de source vers chaque sommet. Utilisez -1 pour les sommets inaccessibles. Supposez qu'il n'y a pas de cycle négatif.

Relaxez toutes les arêtes n - 1 fois.

Essayez vous-même

#include <stdlib.h>

int* bellmanFord(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Écrire le code ici
    *returnSize = 0;
    return edges;
}

Testez-vous

Cette 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

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo Code Implementation (Part 1)Implementation (Part 2) Leçon de projet

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2