()
| 6 | |
| 7 | |
| 8 | def test_johnson_basic(): |
| 9 | g = { |
| 10 | 0: [(1, 3), (2, 8), (4, -4)], |
| 11 | 1: [(3, 1), (4, 7)], |
| 12 | 2: [(1, 4)], |
| 13 | 3: [(0, 2), (2, -5)], |
| 14 | 4: [(3, 6)], |
| 15 | } |
| 16 | dist = johnson(g) |
| 17 | assert math.isclose(dist[0][3], 2.0, abs_tol=1e-9) |
| 18 | assert math.isclose(dist[3][2], -5.0, abs_tol=1e-9) |
| 19 | |
| 20 | |
| 21 | def test_johnson_negative_cycle(): |