Algoritmo de Brandes

Em computação, o algoritmo de Brandes é um algoritmo utilizado para cálcular a intermediação de todos os vértices de um grafo sem pesos. Sua complexidade é ${\displaystyle O(|V||E|)}$ em tempo e ${\displaystyle O(|V|+|E|)}$ em espaço, aonde ${\displaystyle V}$ é o conjunto de vértices e ${\displaystyle E}$ o conjunto de arestas de um grafo ${\displaystyle G}$.^[1] Comparado a algoritmos anteriores que rodavam em tempo ${\displaystyle O(|V|^{3})}$ ele permite o processamento de redes muito mais complexas do que antes possível.

${\displaystyle C_{b}\leftarrow 0,v\in V;}$
${\displaystyle \mathbf {for} \ s\in V\ \mathbf {do} }$
    ${\displaystyle S\leftarrow {\mbox{pilha vazia}};}$
    ${\displaystyle P[w]\leftarrow {\mbox{lista vazia}},w\in V;}$
    ${\displaystyle \sigma [t]\leftarrow 0,t\in V;\sigma [s]\leftarrow 1;}$
    ${\displaystyle d[t]\leftarrow -1,t\in V;d[s]\leftarrow 0;}$
    ${\displaystyle Q\leftarrow {\mbox{fila vazia}};}$
    ${\displaystyle enfilerar\ s\rightarrow Q;}$
    ${\displaystyle \mathbf {while} \ Q\ nao\ for\ vazio\ \mathbf {do} }$
        ${\displaystyle desenfilerar\ v\leftarrow Q;}$
        ${\displaystyle push\ v\rightarrow S;}$
        ${\displaystyle \mathbf {foreach} \ vizinho\ w\ de\ v\ \mathbf {do} }$
            ${\displaystyle //\ w\ encontrado\ pela\ primeira\ vez?}$
            ${\displaystyle \mathbf {if} \ d[w]<0\ \mathbf {then} }$
                ${\displaystyle enfilerar\ w\rightarrow Q;}$
                ${\displaystyle d[w]\leftarrow d[v]+1;}$
            ${\displaystyle \mathbf {end} }$
            ${\displaystyle //\ menor\ caminho\ ate\ w\ por\ v?}$
            ${\displaystyle \mathbf {if} \ d[w]=d[v]+1\ \mathbf {then} }$
                ${\displaystyle \sigma [w]\leftarrow \sigma [w]+\sigma [v];}$
                ${\displaystyle adicionarv\rightarrow P[w];}$
            ${\displaystyle \mathbf {end} }$
        ${\displaystyle \mathbf {end} }$
    ${\displaystyle \mathbf {end} }$
    ${\displaystyle \delta [v]\leftarrow 0,v\in V;}$
    ${\displaystyle //\ S\ retorna\ os\ vertices\ em\ ordem\ nao-crescente\ da\ distancia\ a\ partir\ de\ s}$
    ${\displaystyle \mathbf {while} \ S\ nao\ for\ vazio\ \mathbf {do} }$
        ${\displaystyle pop\ w\leftarrow S;}$
        ${\displaystyle \mathbf {for} \ v\in P[w]\ \mathbf {do} \ \delta [v]\leftarrow \delta [v]+{\frac {\sigma [v]}{\sigma [w]}}\cdot (1+\delta [w]);}$
        ${\displaystyle \mathbf {if} \ w\neq s\ \mathbf {then} \ C_{b}[w]\leftarrow C_{b}[w]+\delta [w];}$
    ${\displaystyle \mathbf {end} }$
${\displaystyle \mathbf {end} }$

Referências

Centralidade Intermediação