mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
a9f2e72541
* Fix typos in Johnson's algorithm (nd -> and) to pass codespell * Rename type aliases and h parameter to follow snake_case and descriptive naming * Potential fix for pull request finding Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com> --------- Co-authored-by: John Law <johnlaw.po@gmail.com> Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: Copilot Autofix powered by AI <175728472+Copilot@users.noreply.github.com>
25 lines
509 B
Python
25 lines
509 B
Python
import math
|
|
|
|
import pytest
|
|
|
|
from graphs.johnson import johnson
|
|
|
|
|
|
def test_johnson_basic():
|
|
g = {
|
|
0: [(1, 3), (2, 8), (4, -4)],
|
|
1: [(3, 1), (4, 7)],
|
|
2: [(1, 4)],
|
|
3: [(0, 2), (2, -5)],
|
|
4: [(3, 6)],
|
|
}
|
|
dist = johnson(g)
|
|
assert math.isclose(dist[0][3], 2.0, abs_tol=1e-9)
|
|
assert math.isclose(dist[3][2], -5.0, abs_tol=1e-9)
|
|
|
|
|
|
def test_johnson_negative_cycle():
|
|
g2 = {0: [(1, 1)], 1: [(0, -3)]}
|
|
with pytest.raises(ValueError):
|
|
johnson(g2)
|