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"]
IGDistanceMatrix
function from IGraph/M as a workaround until this gets fixed. $\endgroup$ – Szabolcs Apr 17 '18 at 6:44