GraphDistance error when Graph vertices are Associations

Sadly, this another one in a long row of issues with noninteger vertices for Graph where things neither work as documented nor as they should. Since GraphDistance is a kernel function, we non-insiders cannot tell why this happens. (But every now and then, associations are interpreted as list of rules; e.g. when used as second argument of ReplaceAll.)

What I can do for you is to provide a way to circumvent that by using integer vertices and the associations as vertex labels. For looking up a vertex from its label, we employ an association a.

edgelist = {<|"n" -> 1|> -> <|"n" -> 2|>, <|"n" -> 1|> -> <|"n" -> 3|>, <|"n" -> 2|> -> <|"n" -> 4|>, <|"n" -> 3|> -> <|"n" -> 4|>};   
vertexlist = Sort[DeleteDuplicates[Flatten[List @@@ edgelist]]];
a = AssociationThread[vertexlist, Range[Length[vertexlist]]];

Visuably, we obtain the same graph:

g = Graph[
  Map[a, edgelist, {2}],
  VertexLabels -> KeyValueMap[{key, val} \[Function] val -> key, a]
  ]

In calls to Graph-related function that require vertices as argument, we have to insert the lookup function a:

GraphDistance[g, a[<|"n" -> 2|>], a[<|"n" -> 4|>]]

1

This is clearly a bug, and as Henrik said, a fairly common type of bug, unfortunately. When you encounter such problems, please do report them to Wolfram.

As a workaround, you can use IGDistanceMatrix from my IGraph/M package.

<<IGraphM`

IGDistanceMatrix[g, {<|"n" -> 2|>}, {<|"n" -> 4|>}]
(* {{1}} *)

This function takes only lists of vertices as the 2nd and 3rd argument. It does not take single vertex names. This is a mild inconvenience, but on the upside, it eliminates any ambiguities whether an expression is a vertex list or a single vertex name that happens to be a list (or association or whatever).