Pseudo Code

Lição 4 de 9 do curso Algoritmo de Bellman-Ford - Algoritmos de Grafos da Coddy.

bellmanFord(n, edges, source):
   dist = [INF, INF, ...]; dist[source] = 0
   repeat (n - 1) times:
      for each edge (u -> v, weight w):
         if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
   replace every remaining INF with -1
   return dist

// ciclo negativo: após n-1 passagens, se qualquer aresta AINDA relaxar,
// um ciclo negativo existe.

A guarda dist[u] != INF nos impede de construir caminhos a partir de vértices inalcançáveis.
Relaxar toda a lista de arestas é uma passagem. Bellman-Ford é apenas essa passagem repetida n - 1 vezes.

Experimente você mesmo

Esta lição não inclui um desafio de código.

Teste seus conhecimentos

Esta 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

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