Seidel’s shortest path algorithm implementation for Computational Complexity Theory 2021 course (HSE)
Algorithm implementation is in seidel_algo.py file.
It receives an adjacency matrix as input and returns distance matrix as output. For unreachable vertexes the distance equals 0.
File for building automated testing workflow: python-package.yml
A - adjacency matrix with size n
 - adjacency matrix with 1s on diagonal
G - graph
D - distance matrix
- Find Â^1, Â^2, Â^4... Â^n1 where n1 >= n
- D of G^n1 = A^n1 (with zeros on diagonal)
- Find by special rule D of G^n1 -> D of G^n1 / 2 -> ... -> D of G^2 -> D of G
- Return D of G
Load dependencies:
pip install -r requirements.txt
Run algorithm with example input:
python seidel_algo.py
Run tests:
py.test -v test_seidel.py