Ok, I think the response is given by the fact that Dijkstra algorithm doesnt handle negative weights and the random data generated produce negative weights sometimes. I think it would be useful if it could give a warning in next releases of Mathematica
