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)
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$.
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:
Que grafos são esses?
(sua resposta)
In [ ]:
# sua resposta