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 é $O(|V||E|)$ em tempo e $O(|V|+|E|)$ em espaço, aonde $V$ é o conjunto de vértices e $E$ o conjunto de arestas de um grafo $G$. Comparado a algoritmos anteriores que rodavam em tempo $O(|V{|}^3)$ ele permite o processamento de redes muito mais complexas do que antes possível.

Algoritmo

$C_b\leftarrow 0,v\in V;$
$𝐟𝐨𝐫s\in V𝐝𝐨$
    $S\leftarrow \text{pilha vazia};$
    $P[w]\leftarrow \text{lista vazia},w\in V;$
    $\sigma [t]\leftarrow 0,t\in V;\sigma [s]\leftarrow 1;$
    $d[t]\leftarrow -1,t\in V;d[s]\leftarrow 0;$
    $Q\leftarrow \text{fila vazia};$
    $enfilerars\to Q;$
    $𝐰𝐡𝐢𝐥𝐞Qnaoforvazio𝐝𝐨$
        $desenfilerarv\leftarrow Q;$
        $pushv\to S;$
        $𝐟𝐨𝐫𝐞𝐚𝐜𝐡vizinhowdev𝐝𝐨$
            $//wencontradopelaprimeiravez?$
            $𝐢𝐟d[w]<0𝐭𝐡𝐞𝐧$
                $enfilerarw\to Q;$
                $d[w]\leftarrow d[v]+1;$
            $𝐞𝐧𝐝$
            $//menorcaminhoatewporv?$
            $𝐢𝐟d[w]=d[v]+1𝐭𝐡𝐞𝐧$
                $\sigma [w]\leftarrow \sigma [w]+\sigma [v];$
                $adicionarv\to P[w];$
            $𝐞𝐧𝐝$
        $𝐞𝐧𝐝$
    $𝐞𝐧𝐝$
    $\delta [v]\leftarrow 0,v\in V;$
    $//Sretornaosverticesemordemnao-crescentedadistanciaapartirdes$
    $𝐰𝐡𝐢𝐥𝐞Snaoforvazio𝐝𝐨$
        $popw\leftarrow S;$
        $𝐟𝐨𝐫v\in P[w]𝐝𝐨\delta [v]\leftarrow \delta [v]+\frac{\sigma [v]}{\sigma [w]}\cdot (1+\delta [w]);$
        $𝐢𝐟w\ne s𝐭𝐡𝐞𝐧C_b[w]\leftarrow C_b[w]+\delta [w];$
    $𝐞𝐧𝐝$
$𝐞𝐧𝐝$

Ver também

Centralidade Intermediação