Implementacja (część 1)

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

Najpierw pojedynczy przebieg relaksacji wszystkich krawędzi.

Wyzwanie

Średni

Bellman-Ford to tylko jedna operacja powtarzana wielokrotnie: przebieg relaksacji wszystkich krawędzi. Zbudujmy pojedynczy przebieg.

Napisz funkcję o nazwie relaxAll, która przyjmuje n, płaską tablicę edges (trójki, skierowane, mogą mieć ujemne wagi) oraz source. Zacznij od dist[source] = 0, a pozostałym wierzchołkom przypisz nieskończoność, a następnie zrelaksuj każdą krawędź dokładnie raz (w podanej kolejności) i zwróć uzyskane odległości, używając -1 dla wierzchołków, do których nadal nie można dotrzeć.

Ponieważ jest to tylko jeden przebieg, wierzchołki osiągalne wyłącznie przez kilka krawędzi mogą nadal mieć wartość -1. To oczekiwane zachowanie.

Spróbuj swoich sił

#include <stdlib.h>

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