C
b
←
0
,
v
∈
V
;
{\displaystyle C_{b}\leftarrow 0,v\in V;}
f
o
r
s
∈
V
d
o
{\displaystyle \mathbf {for} \ s\in V\ \mathbf {do} }
S
←
pilha vazia
;
{\displaystyle S\leftarrow {\mbox{pilha vazia}};}
P
[
w
]
←
lista vazia
,
w
∈
V
;
{\displaystyle P[w]\leftarrow {\mbox{lista vazia}},w\in V;}
σ
[
t
]
←
0
,
t
∈
V
;
σ
[
s
]
←
1
;
{\displaystyle \sigma [t]\leftarrow 0,t\in V;\sigma [s]\leftarrow 1;}
d
[
t
]
←
−
1
,
t
∈
V
;
d
[
s
]
←
0
;
{\displaystyle d[t]\leftarrow -1,t\in V;d[s]\leftarrow 0;}
Q
←
fila vazia
;
{\displaystyle Q\leftarrow {\mbox{fila vazia}};}
e
n
f
i
l
e
r
a
r
s
→
Q
;
{\displaystyle enfilerar\ s\rightarrow Q;}
w
h
i
l
e
Q
n
a
o
f
o
r
v
a
z
i
o
d
o
{\displaystyle \mathbf {while} \ Q\ nao\ for\ vazio\ \mathbf {do} }
d
e
s
e
n
f
i
l
e
r
a
r
v
←
Q
;
{\displaystyle desenfilerar\ v\leftarrow Q;}
p
u
s
h
v
→
S
;
{\displaystyle push\ v\rightarrow S;}
f
o
r
e
a
c
h
v
i
z
i
n
h
o
w
d
e
v
d
o
{\displaystyle \mathbf {foreach} \ vizinho\ w\ de\ v\ \mathbf {do} }
/
/
w
e
n
c
o
n
t
r
a
d
o
p
e
l
a
p
r
i
m
e
i
r
a
v
e
z
?
{\displaystyle //\ w\ encontrado\ pela\ primeira\ vez?}
i
f
d
[
w
]
<
0
t
h
e
n
{\displaystyle \mathbf {if} \ d[w]<0\ \mathbf {then} }
e
n
f
i
l
e
r
a
r
w
→
Q
;
{\displaystyle enfilerar\ w\rightarrow Q;}
d
[
w
]
←
d
[
v
]
+
1
;
{\displaystyle d[w]\leftarrow d[v]+1;}
e
n
d
{\displaystyle \mathbf {end} }
/
/
m
e
n
o
r
c
a
m
i
n
h
o
a
t
e
w
p
o
r
v
?
{\displaystyle //\ menor\ caminho\ ate\ w\ por\ v?}
i
f
d
[
w
]
=
d
[
v
]
+
1
t
h
e
n
{\displaystyle \mathbf {if} \ d[w]=d[v]+1\ \mathbf {then} }
σ
[
w
]
←
σ
[
w
]
+
σ
[
v
]
;
{\displaystyle \sigma [w]\leftarrow \sigma [w]+\sigma [v];}
a
d
i
c
i
o
n
a
r
v
→
P
[
w
]
;
{\displaystyle adicionarv\rightarrow P[w];}
e
n
d
{\displaystyle \mathbf {end} }
e
n
d
{\displaystyle \mathbf {end} }
e
n
d
{\displaystyle \mathbf {end} }
δ
[
v
]
←
0
,
v
∈
V
;
{\displaystyle \delta [v]\leftarrow 0,v\in V;}
/
/
S
r
e
t
o
r
n
a
o
s
v
e
r
t
i
c
e
s
e
m
o
r
d
e
m
n
a
o
−
c
r
e
s
c
e
n
t
e
d
a
d
i
s
t
a
n
c
i
a
a
p
a
r
t
i
r
d
e
s
{\displaystyle //\ S\ retorna\ os\ vertices\ em\ ordem\ nao-crescente\ da\ distancia\ a\ partir\ de\ s}
w
h
i
l
e
S
n
a
o
f
o
r
v
a
z
i
o
d
o
{\displaystyle \mathbf {while} \ S\ nao\ for\ vazio\ \mathbf {do} }
p
o
p
w
←
S
;
{\displaystyle pop\ w\leftarrow S;}
f
o
r
v
∈
P
[
w
]
d
o
δ
[
v
]
←
δ
[
v
]
+
σ
[
v
]
σ
[
w
]
⋅
(
1
+
δ
[
w
]
)
;
{\displaystyle \mathbf {for} \ v\in P[w]\ \mathbf {do} \ \delta [v]\leftarrow \delta [v]+{\frac {\sigma [v]}{\sigma [w]}}\cdot (1+\delta [w]);}
i
f
w
≠
s
t
h
e
n
C
b
[
w
]
←
C
b
[
w
]
+
δ
[
w
]
;
{\displaystyle \mathbf {if} \ w\neq s\ \mathbf {then} \ C_{b}[w]\leftarrow C_{b}[w]+\delta [w];}
e
n
d
{\displaystyle \mathbf {end} }
e
n
d
{\displaystyle \mathbf {end} }
Referências