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,\hat{I}»/n)$ where each edge is independently assigned a random signed weight. For two uniformly chosen vertices, we study the jo…