Implementation (Part 1)
Lição 5 de 9 do curso Algoritmo de Bellman-Ford - Algoritmos de Grafos da Coddy.
Primeiro, uma única passagem de relaxamento sobre todas as arestas.
Desafio
MédioBellman-Ford é apenas uma operação repetida: um passo de relaxamento sobre todas as arestas. Vamos construir um único passo.
Escreva uma função chamada relaxAll que recebe n, o array plano edges (triplas, direcionadas, possivelmente negativas) e um source. Comece com dist[source] = 0 e todos os outros no infinito, então relaxe cada aresta uma vez (na ordem fornecida) e retorne as distâncias resultantes, usando -1 para vértices que ainda não foram alcançados.
Como é apenas um passo, vértices alcançáveis apenas através de várias arestas ainda podem ser -1. Isso é esperado.
Experimente você mesmo
#include <stdlib.h>
int* relaxAll(int n, int* edges, int edges_size, int source, int* returnSize) {
// Escreva o código aqui
*returnSize = 0;
return edges;
}
Teste seus conhecimentosEsta lição inclui um quiz rápido. Comece a lição para respondê-lo e acompanhar seu progresso.
Todas as lições de Algoritmo de Bellman-Ford - Algoritmos de Grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity