Tantangan Akhir #1

Pelajaran 8 dari 9 dalam kursus Algoritma Bellman-Ford: Algoritma Graf di Coddy.

Tantangan

Sedang

Kekuatan super Bellman-Ford adalah mendeteksi siklus negatif.

Tulis fungsi bernama hasNegativeCycle yang menerima n dan array edges datar (tripel, berarah), lalu mengembalikan 1 jika graf berisi siklus berbobot negatif, atau 0 jika tidak.

Petunjuk: mulai dengan setiap jarak bernilai 0, lakukan relaksasi pada semua edge sebanyak n - 1 kali, lalu lakukan satu kali lagi. Jika masih ada edge yang dapat direlaksasi, berarti ada siklus negatif.

Coba sendiri

#include <stdlib.h>

int hasNegativeCycle(int n, int* edges, int edges_size) {
    // Tulis kodemu di sini
    return -1;
}

Semua pelajaran di Algoritma Bellman-Ford: Algoritma Graf

1Pengenalan

Pengenalan Motivasi

2Algoritma

Bagaimana cara kerjanya?Pseudocode Implementasi (Bagian 1)Implementasi (Bagian 2)

Kompleksitas Waktu dan Ruang

3Tantangan Akhir

Tantangan Akhir #1Tantangan Akhir #2

Latihan sendiri: Compiler C online