Implementation (Part 1)

Lektion 5 von 9 im Kurs Bellman-Ford-Algorithmus - Graphenalgorithmen von Coddy.

Zuerst ein einzelner Relaxationsdurchlauf über alle Kanten.

Aufgabe

Mittel

Bellman-Ford ist nur eine wiederholte Operation: ein Relaxationsschritt über alle Kanten. Lassen Sie uns einen einzelnen Durchlauf bauen.

Schreiben Sie eine Funktion namens relaxAll, die n, das flache edges-Array (Tripel, gerichtet, möglicherweise negativ) und eine source entgegennimmt. Beginnen Sie mit dist[source] = 0 und allen anderen auf Unendlich, relaxieren Sie dann jede Kante einmal (in der angegebenen Reihenfolge) und geben Sie die resultierenden Distanzen zurück, wobei -1 für noch nicht erreichte Knoten verwendet wird.

Da es sich nur um einen Durchlauf handelt, können Knoten, die nur über mehrere Kanten erreichbar sind, immer noch -1 sein. Das wird erwartet.

Probier es selbst

#include <stdlib.h>

int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Code hier schreiben
    *returnSize = 0;
    return edges;
}

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Bellman-Ford-Algorithmus - Graphenalgorithmen

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2