Hello all,

I am currently working on a code where I generate a random graph using Mathematica and attempt to find the shortest path between two vertices. While the code seems to work well in some instances, I have noticed that there are cases where it fails to find a valid shortest path.

Here is the code I am using:

n = 35;

u1 = RandomReal[{-15, 15}, n];
u2 = RandomReal[{-15, 15}, n];
u3 = RandomReal[{0, 1}, n];

nnG = NearestNeighborGraph[Transpose[{u1, u2}], 10, 
   DirectedEdges -> False, DistanceFunction -> EuclideanDistance];

M = AdjacencyMatrix@nnG;

{l1, l2} = Dimensions@M;

f[x1_, x2_] := (x1 + x2)/2;

W = Normal@
     M (DistanceMatrix[Transpose[{u1, u2}], 
       DistanceFunction -> EuclideanDistance] - 
      Parallelize@Outer[f, u3, u3]) /. Rule[0., \[Infinity]];

nnGw = WeightedAdjacencyGraph[W, 
   VertexCoordinates -> Transpose[{u1, u2}]];

GraphPlot[
 HighlightGraph[nnGw, 
  PathGraph@FindShortestPath[nnGw, 1, 10, Method -> "Dijkstra"]], 
 EdgeStyle -> Opacity[0.1], VertexStyle -> PointSize[0.004]]

I suspect that the issue may be related to the random data generated, but I am uncertain about the underlying cause. I would greatly appreciate any insights or suggestions you might have to help me understand and resolve this inconsistency in finding the shortest path.

Thank you in advance for your assistance!