3. Arc(5, 3) is changed to be infinity since it cannot be included in the solution.Without Arc(3, 5), the lower bound is 99+18=117
4. Step 2.1: Choose Arc(2, 1) and Arc(1, 2) is changed to be infinity since it cannot be included in the solution.Step 2.1: Without Arc(2, 1), the lower bound is 99+26=125Step 3: With Arc(2, 1), total cost reduced: 99 + 9 + 4 = 112 (new lower bound).
5. Arc(1, 2) is changed to be infinity since it cannot be included in the solution.Without Arc(2, 1), the lower bound is 99+26=125
6. Step 2.1: Choose Arc(1, 4) and Arc(4, 1) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(1, 4), the lower bound is 112+41=153Step 3: With Arc(1, 4), total cost reduced: 112 + 14 = 126 (new lower bound).
7. Step 2.1: Choose Arc(1, 4) and Arc(4, 1) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(1, 4), the lower bound is 112+41=153Step 3: With Arc(1, 4), total cost reduced: 112 + 14 = 126 (new lower bound).
8. Without Arc(1, 4), the lower bound is 112+41=153
9. Step 2.1: Choose Arc(6, 7) and Arc(7, 6) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(6, 7), the lower bound is 126+15=141Step 3: With Arc(6, 7), total cost reduced: 126 + 0 = 126 (new lower bound).
10. L. B. = 99
11. Step 2.1: Choose Arc(5, 2) and Arc(2, 5) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(5, 2), no way to go, no solution!!!Step 3: With Arc(5, 2), total cost reduced: 126 + 0 = 126 (new lower bound).
12. L. B. = 99
13. Step 2.1: Choose Arc(5, 2) and Arc(2, 5) is changed to be infinity since it cannot be included in the solution. Step 2.2: Without Arc(5, 2), no way to go, no solution!!!Step 3: With Arc(5, 2), total cost reduced: 126 + 0 = 126 (new lower bound).
Prev