Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
<|reference_start|>Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall: The celebrated Floyd-Warshall algorithm efficiently computes the all-pairs shortest path, and its simplicity made it a staple in computer science classes. Frequently, students discover a variant of this Floyd-Warshall algorithm by mixing up the loop order, ending up with the incorrect APSP matrix. This paper considers a computational problem of computing this incorrect APSP matrix. We will propose efficient algorithms for this problem and prove that this incorrect variant is APSP-complete.<|reference_end|>
@article{koo2024anarchy,
    title={Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation
  of Floyd-Warshall},
    author={Jaehyun Koo},
    journal={arXiv preprint arXiv:2404.08173},
    year={2024},
    doi={10.4230/LIPIcs.FUN.2024.19},
    archivePrefix={arXiv},
    eprint={2404.08173},
    primaryClass={cs.DS}
}