ResearchBenchmarksElementary Shortest Path with Negative Cycles on Erdős-Rényi (ER) graphs n=200Follow-151.17Best Path CostNCP-157.0556-117.3278-77.6-37.8722Jul 1, 2026Evaluation ResultsMethodMethodLinksBest Path CostTime (s)NCP2026.07-151.170.818Beam-256beam size=256beam size=2562026.07-103.1430.01Beam-512beam size=512beam size=5122026.07-103.111.572LP+Dec.2026.07-102.570.92Erdos2026.07-4.030.029