Implementation (Part 1)

Lesson 5 of 9 in Coddy's Bellman-Ford Algorithm - Graph Algorithms course.

First, a single relaxation pass over all edges.

Challenge

Medium

Bellman-Ford is just one operation repeated: a relaxation pass over all edges. Let's build a single pass.

Write a function named relaxAll that takes n, the flat edges array (triples, directed, possibly negative), and a source. Start with dist[source] = 0 and all others at infinity, then relax every edge once (in the given order) and return the resulting distances, using -1 for vertices still unreached.

Because it is only one pass, vertices reachable only through several edges may still be -1. That is expected.

Try it yourself

#include <stdlib.h>

int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
    // Write code here
    *returnSize = 0;
    return edges;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Bellman-Ford Algorithm - Graph Algorithms

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