Encontro 02, Parte 3: Algoritmo de Bellman-Ford

Este guia foi escrito para ajudar você a atingir os seguintes objetivos:

  • implementar o algoritmo de Bellman-Ford;
  • praticar o uso da biblioteca da disciplina.

Primeiramente, vamos importar a biblioteca:


In [ ]:
import sys
sys.path.append('..')

import socnet as sn

A seguir, vamos configurar as propriedades visuais:


In [ ]:
sn.graph_width = 320
sn.graph_height = 180

Por fim, vamos carregar e visualizar um grafo:


In [ ]:
g = sn.load_graph('3-bellman.gml', has_pos=True)

for n, m in g.edges():
    g.edge[n][m]['label'] = g.edge[n][m]['c']

sn.show_graph(g, elab=True)

Passeios de custo mínimo

O arquivo atribui c às arestas. Formalmente, esse atributo é uma função que mapeia pares de nós a reais:

$c \colon N \times N \rightarrow \mathbb{R}$.

O custo de um passeio $\langle n_0, n_1, \ldots, n_{k-1} \rangle$ é

$\sum^{k-2}_{i=0} c(n_i, n_{i+1})$.

Um passeio de origem $s$ e destino $t$ tem custo mínimo se não existe outro passeio de origem $s$ e destino $t$ de custo menor. Note que podem existir múltiplos passeios de custo mínimo.

A distância ponderada de $s$ a $t$ é o custo mínimo de um passeio de origem $s$ e destino $t$. Por completude, dizemos que a distância ponderada de $s$ a $t$ é $\infty$ se não existe passeio de origem $s$ e destino $t$.

Algoritmo de Bellman-Ford

Dado um nó $s$, podemos eficientemente calcular as distâncias ponderadas desse a todos os outros nós do grafo usando o algoritmo de Bellman-Ford. A ideia desse algoritmo é diferente da ideia do algoritmo de busca em largura, mas também é simples: inicializamos a distância de $s$ como $0$, inicializamos a distância dos outros nós como $\infty$ e verificamos todas as arestas. Para cada aresta $(n, m)$, se a distância de $m$ for maior que a distância de $n$ mais o custo de $(n, m)$, essa soma passa a ser a nova distância de $m$.

É possível demonstrar matematicamente esse laço precisa ser repetido não mais que $|N|-1$ vezes, onde $|N|$ é a quantidade de nós.


In [ ]:
from math import inf, isinf

s = 0

for n in g.nodes():
    g.node[n]['d'] = inf

g.node[s]['d'] = 0

for i in range(g.number_of_nodes() - 1):
    for n, m in g.edges():
        d = g.node[n]['d'] + g.edge[n][m]['c']

        if g.node[m]['d'] > d:
            g.node[m]['d'] = d

for n in g.nodes():
    print('distância de {}: {}'.format(n, g.node[n]['d']))

No entanto, essa demonstração depende de certas hipóteses em relação ao grafo. Tenho uma má e uma boa notícia:

  • a má é que existem grafos em que o algoritmo não funciona, ou seja, devolve uma resposta incorreta;
  • a boa é que, nos grafos em que ele funciona, os passeios de custo mínimo são caminhos de custo mínimo.

Exercício 1

Que grafos são esses?

(sua resposta)

Exercício 2

Monte uma visualização do algoritmo de Bellman-Ford.


In [ ]:
# sua resposta