Implementacja (część 2)

Lekcja 6 z 9 w kursie Algorytm Bellmana-Forda — algorytmy grafowe w Coddy.

Teraz powtarzaj przebieg, aż odległości będą ostateczne.

Wyzwanie

Średni

Oto cały algorytm: powtarzaj przebieg relaksacji, aż odległości przestaną się zmieniać.

Napisz funkcję o nazwie bellmanFord, która przyjmuje n, płaską tablicę edges (trójki, skierowane, możliwe ujemne wartości) oraz source, i zwraca najkrótszą odległość od source do każdego wierzchołka. Dla nieosiągalnych wierzchołków użyj -1. Załóż, że nie ma ujemnego cyklu.

Relaksuj wszystkie krawędzie n - 1 razy.

Spróbuj swoich sił

#include <stdlib.h>

int* bellmanFord(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = 0;
    return edges;
}