GraphDistance gives incorrect result in weighted multigraph

Question

Bug introduced in 10.0 and fixed in 12.0
Multigraph support was introduced in 10.0

---

GraphDistance and GraphDistanceMatrix return incorrect results for the following weighted multigraphs. Is there a workaround?

g = Graph[{1 <-> 2, 1 <-> 3, 2 <-> 1, 2 <-> 3}, 
   EdgeWeight -> {3, 3, 2, 1}, VertexLabels -> "Name"];

There are two edges between vertices 1 and 2. One of these edges has weight 3, the other weight 2.

The shortest path length between 1 and 2 is calculated as:

{GraphDistance[g, 1, 2], GraphDistance[g, 2, 1]}

(* {3., 5.} *)

GraphDistanceMatrix[g] // MatrixForm

|0.  3.  3.|
|5.  0.  1.|
|5.  1.  0.|

The shortest distance between 1 and 2 is not the same as the shortest distance between 2 and 1. Also, the distance matrix is not symmetric. Finally, neither 3, nor 5 is a correct result here. It should be 2.

Is there a workaround for computing shortest paths in weighted multigraphs?

---

Finally, edge weights are displayed incorrectly in the following:

SetProperty[g, EdgeLabels -> "EdgeWeight"]

Answer 1

One possible workaround is to use IGDistanceMatrix from the IGraph/M package.

IGDistanceMatrix[g]
(* {{0., 2., 3.}, {2., 0., 1.}, {3., 1., 0.}} *)

Another workaround is to convert the multi-graph to a simple graph and keep only the smallest weight for parallel edges.

Again IGraph/M has a function for this.

IGWeightedSimpleGraph[g, Min]

The distance matrix:

GraphDistanceMatrix@IGWeightedSimpleGraph[g, Min]
(* {{0., 2., 3.}, {2., 0., 1.}, {3., 1., 0.}} *)

Finally, we could do the same without IGraph/M, though the performance won't be nearly as good.

weightedSimpleEdges = 
 Min /@ GroupBy[
   Transpose@{Sort /@ EdgeList[g], PropertyValue[g, EdgeWeight]},
   First -> Last
 ]
(* <|1 \[UndirectedEdge] 2 -> 2, 1 \[UndirectedEdge] 3 -> 3, 2 \[UndirectedEdge] 3 -> 1|> *)

GraphDistanceMatrix@Graph[
  VertexList[g], 
  Keys[weightedSimpleEdges], 
  EdgeWeight -> Values[weightedSimpleEdges]
]
(* {{0., 2., 3.}, {2., 0., 1.}, {3., 1., 0.}} *)