This paper presents a new deterministic algorithm for the single-source shortest paths (SSSP) problem on real non-negative edge-weighted directed graphs, with running time O(m√{log n} + √{mnlog nlog log n}), which is O(m√{log nlog log n}) for sparse graphs. This improves the recent breakthrough result of O(m log^{2/3} n) time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].

In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m \sqrt{\log n \cdot \log \log n})$ in the comparison-addition model. This is the first algorithm to break the $O(m+n \log n)$ time bound for real-weighted sparse graphs by Dijkstra’s algorithm with Fibonacci heaps. Previous undirected nonnegative SSSP algorithms give time bound of $O(m \alpha(m, n)+ \min \{n \log n, n \log \log r\})$ in comparison-addition model, where $\alpha$ is the inverse-Ackermann function and r is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of $\Omega(m+\min \{n \log n, n \log \log r\})$ for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchybased approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.

We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. This paper introduces two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting, and improve the competitive ratios to 0.716, from 0.711 and 0.7 respectively. For edge-weighted matching with free disposal, we propose the Top Half Sampling algorithm. We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality. This improves the competitive ratio to 0.706, breaking the 1−1/e barrier in this setting for the first time in the literature. Finally, for the harder edge-weighted problem without free disposal, we prove that no algorithms can be 0.703 competitive, separating this setting from the aforementioned three.

We study the online stochastic matching problem. Consider a bipartite graph with offline vertices on one side, and with i.i.d.online vertices on the other side. The offline vertices and the distribution of online vertices are known to the algorithm beforehand. The realization of the online vertices, however, is revealed one at a time, upon which the algorithm immediately decides how to match it. For maximizing the cardinality of the matching, we give a 0.711-competitive online algorithm, which improves the best previous ratio of 0.706. When the offline vertices are weighted, we introduce a 0.7009-competitive online algorithm for maximizing the total weight of the matched offline vertices, which improves the best previous ratio of 0.662.