Implementation (Part 2)
Lição 6 de 9 do curso Algoritmo de Bellman-Ford - Algoritmos de Grafos da Coddy.
Agora repita o passo até que as distâncias sejam definitivas.
Desafio
MédioAgora o algoritmo completo: repita o passo de relaxamento até que as distâncias se estabilizem.
Escreva uma função chamada bellmanFord que receba n, o array plano edges (triplas, direcionadas, possivelmente negativas) e um source, e retorne a distância mais curta de source para cada vértice. Use -1 para vértices inalcançáveis. Assuma que não há ciclos negativos.
Relaxe todas as arestas n - 1 vezes.
Experimente você mesmo
#include <stdlib.h>
int* bellmanFord(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