Complex Networks

86 

Complex Networks: An Algorithmic Perspective

executed n times resulting in O(n

3

) time including initialization which also takes n

2

steps.

Algorithm 5.2 FW APSP

1: S ← Ø

2: for all {u,v} ∈V do ⊲ initialize

3: if u = v then

4: D[u,v] ← Ø, P[u, v] ← ⊥

5: else if (u,v) ∈ E then

6: D[u,v] ← w

uv

, P[u,v] ← v

7: else D[u, v] ← ∞, P[u, v] ← ⊥

8: end if

9: end for

10: while S 6= V do

11: pick w from V \S

12: for all u ∈V do ⊲ Execute a global w-pivot

13: for all v ∈V do ⊲ Execute a local w-pivot at u

14: if D[u,w] + D[w,v] < D[u, v] then

15: D[u,v] ← D[u,w] + D[w, v]

16: P[u,v] ← P[u,w]

17: end if

18: end for

19: end for

20: S ← S ∪ {w}

21: end while

Example

Figure 5.4 shows ...