Wyzwanie końcowe nr 1

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

Wyzwanie

Średni

Supermocą algorytmu Bellmana-Forda jest wykrywanie ujemnych cykli.

Napisz funkcję o nazwie hasNegativeCycle, która przyjmuje n oraz płaską tablicę edges (trójki, krawędzie skierowane) i zwraca 1, jeśli graf zawiera cykl o ujemnej wadze, lub 0 w przeciwnym razie.

Podpowiedź: ustaw początkowo każdą odległość na 0, rozluźnij wszystkie krawędzie n - 1 razy, a następnie wykonaj jeszcze jeden przebieg. Jeśli nadal można rozluźnić dowolną krawędź, istnieje ujemny cykl.

Spróbuj swoich sił

#include <stdlib.h>

int hasNegativeCycle(int n, int* edges, int edges_size) {
    // Wpisz kod tutaj
    return -1;
}

Wszystkie lekcje w sekcji Algorytm Bellmana-Forda — algorytmy grafowe

1Wprowadzenie

Wprowadzenie Motywacja

2Algorytm

Jak to działa?Pseudokod Implementacja (część 1)Implementacja (część 2)

Złożoność czasowa i pamięciowa

3Wyzwania końcowe

Wyzwanie końcowe nr 1Wyzwanie końcowe nr 2

Poćwicz samodzielnie: Kompilator C online