The research team led by Duan Ran from Tsinghua University's Institute for Interdisciplinary Information Sciences has been honored with the Best Paper Award at the prestigious Symposium on Theory of Computing (STOC) 2025. Their groundbreaking paper, titled "Overcoming the Sorting Barrier for Directed Single-Source Shortest Paths," delves into a cornerstone problem in graph algorithms: the Single-Source Shortest Path Problem (SSSP). By meticulously analyzing the computational costs of the Dijkstra algorithm, the team innovated a hybrid approach that seamlessly integrates Dijkstra's algorithm with the Bellman-Ford algorithm. Furthermore, they devised a sophisticated data structure that facilitates efficient grouped insertions and extractions, thereby markedly enhancing the algorithm's performance.

Duan Ran serves as the corresponding author of this seminal work, with significant contributions from Shu Xinkai, Mao Jiayi, Yin Longhui, alumni of Yao Class, and Mao Xiao, a Ph.D. candidate at Stanford University. This triumph underscores Tsinghua University's formidable research prowess in the realm of theoretical computer science.