n = 50 m = 60 n1 = 4 n2 = 5 16 31 42 17 49 25 8 30 15 48 47 48 23 0 37 38 16 15 31 47 40 31 34 5 39 15 21 19 40 12 42 6 43 36 23 44 14 32 25 29 32 24 24 19 46 40 34 27 37 26 10 23 31 49 40 4 21 30 17 15 38 12 4 12 9 18 46 34 49 30 10 29 38 34 48 36 26 34 10 26 38 43 48 49 10 17 16 48 31 20 40 10 26 40 41 36 21 31 20 22 18 46 6 34 11 19 10 1 31 12 29 8 42 13 30 6 3 21 17 30 +++ The constructed graph 0 -> 23 1 -> 10 2 -> 3 -> 21 4 -> 12, 40 5 -> 34 6 -> 30, 34, 42 7 -> 8 -> 29, 30 9 -> 18 10 -> 1, 40, 17, 26, 29, 23 11 -> 19 12 -> 31, 4, 38, 40 13 -> 42 14 -> 32 15 -> 17, 39, 16, 48 16 -> 48, 15, 31 17 -> 30, 10, 15, 42 18 -> 46, 9 19 -> 11, 24, 21 20 -> 22, 31 21 -> 3, 31, 30, 19 22 -> 20 23 -> 10, 44, 0 24 -> 19, 32 25 -> 29, 49 26 -> 40, 10, 34, 37 27 -> 34 28 -> 29 -> 8, 10, 25 30 -> 17, 6, 49, 21, 8 31 -> 12, 21, 20, 49, 40, 47, 16 32 -> 24, 14 33 -> 34 -> 6, 26, 38, 46, 27, 5 35 -> 36 -> 41, 48, 43 37 -> 26, 38 38 -> 43, 34, 12, 37 39 -> 15 40 -> 26, 10, 4, 46, 12, 31 41 -> 36 42 -> 13, 6, 17 43 -> 38, 36 44 -> 23 45 -> 46 -> 18, 34, 40 47 -> 31, 48 48 -> 16, 49, 36, 47, 15 49 -> 48, 30, 31, 25 +++ Method 1 BFS(0) returns 4 BFS(1) returns 3 BFS(2) returns INFINITY BFS(3) returns 3 --- d(V1,V2) = 3 +++ Method 2 --- The contracted graph 0 -> 23, 21, 10 1 -> 2 -> 3 -> 4 -> 40, 12 5 -> 34 6 -> 42, 34, 30 7 -> 8 -> 30, 29 9 -> 18 10 -> 0, 23, 29, 26, 17, 40 11 -> 19 12 -> 40, 38, 31, 4 13 -> 42 14 -> 32 15 -> 49, 16, 39, 17 16 -> 49, 31, 15 17 -> 42, 30, 15, 10 18 -> 49, 9 19 -> 21, 24, 11 20 -> 31, 22 21 -> 0, 30, 31, 19 22 -> 20 23 -> 0, 44, 10 24 -> 32, 19 25 -> 49, 29 26 -> 37, 34, 40, 10 27 -> 34 28 -> 29 -> 25, 10, 8 30 -> 49, 21, 17, 8, 6 31 -> 49, 40, 21, 20, 16, 12 32 -> 24, 14 33 -> 34 -> 49, 38, 27, 26, 6, 5 35 -> 36 -> 49, 43, 41 37 -> 38, 26 38 -> 43, 37, 34, 12 39 -> 15 40 -> 49, 31, 26, 12, 10, 4 41 -> 36 42 -> 17, 13, 6 43 -> 38, 36 44 -> 23 45 -> 46 -> 47 -> 48 -> 49 -> 40, 36, 34, 31, 30, 25, 18, 16, 15 --- d(V1,V2) = 3