Minimum-Weight Path in a Sparse Erdős--Rényi Graph with Signed Weights

Heng Ma, Pascal Maillard

We consider a sparse Erdős--Rényi graph $\mathcal{G}(n,\lambda /n)$ where each edge is independently assigned a random signed weight. For two uniformly chosen vertices, we study the joint…