# Unexpected data about function GraphDistanceMatrix

This is a weighted undirected graph generated from Excel table data.

DATA=Import["MathData/xx.xlsx"][[1]]//IntegerPart;
edgelist=UndirectedEdge[#1,#2]&@@@ DATA
edgew=#3&@@@ DATA
G=Graph[edgelist,EdgeWeight->edgew,VertexLabels->"Name",EdgeLabels->"EdgeWeight"]
GraphDistanceMatrix[G] // MatrixForm


This is part of the result of GraphDistanceMatrix:

I want to get a shortest distance matrix. Official documentation shows that GraphDistanceMatrix returns the shortest distance matrix, but it is clearly not the case. For example, FindShortestPath[G,5,1], the result is {5,4,2,1}, then the distance should be 910, and 630 is given. I don't know what matrix this is. Am I using something wrong or is this not the shortest distance matrix? Is there a way to get the shortest distance matrix?

• what does VertexList[G] give? – kglr Jun 9 at 5:35
• {1,2,3,4,21,47,5,19,6,7,8,18,9,15,10,11,12,14,13,34,26,16,17,27,25,20,24,22,23,44,45,48,29,30,28,31,42,43,32,36,50,33,35,37,39,40,38,41,46,49} Should it return {1,2,3,4,5,6,...,49,,50}? How do I set it up? The weights of the edges in the Excel table are not given in order. – Mertin Jun 9 at 6:11
• Mertin, for this vertex list, the entry in row 5 and column 1 of the GraphDistanceMatrix is the distance between vertex 21 and vertex 1 (That is,GraphDistance[G, 21, 1] should give 630.) To get the distance between vertex 5 and vertex 1 you need to look at the row corresponding to the position of 5 in VertexList[G], that is, row 7. I posted an answer explaining why. – kglr Jun 9 at 6:40

First an example graph to replicate the issue:

SeedRandom[123]
rg = RandomGraph[{10, 14}];
edges = EdgeList[rg];
ew = Thread[edges -> RandomChoice[Range[10, 100, 10], EdgeCount@rg]];

g1 = Graph[edges, EdgeWeight -> ew,
VertexLabels -> Placed["Name", Center], VertexStyle -> White,
VertexSize -> Medium, EdgeLabels -> "EdgeWeight", ImageSize -> Large]


FindShortestPath[g1, 5, 1]

{5, 10, 4, 1}

GraphDistance[g1, 5, 1]

140.

gdm1 = Round@GraphDistanceMatrix[g1];

MatrixForm[MapAt[Style[#, Blue, Bold] &, gdm1, {5, 1}]]


the ith row (column) in gdm1 corresponds not to vertex i but to the vertex in the ith position in VertexList[g1]:

VertexList[g1]


{1, 3, 4, 7, 2, 9, 6, 8, 10, 5}

If we add the row and column labels to gdm1

MatrixForm[MapAt[Style[#, Blue, Bold] &, gdm1, {5, 1}],


we see that the entry showing the shortest distance between 5 and 1 is at the last row and first column.

To get GraphDistanceMatrix where the entry {i,j} gives the distance between vertices i and j you can re-order the rows and columns of the matrix using Ordering[VertexList @ g1]:

ordering = Ordering[VertexList@g1];

MatrixForm[MapAt[Style[#, Blue, Bold] &, gdm1[[ordering, ordering]], {5, 1}],


Alternatively, you can use the first argument of Graph to specify the vertex list so that the row/column indices of GraphDistanceMatrix coincide with the vertex list:

g2 = Graph[Range[VertexCount[rg]], edges,
EdgeWeight -> ew,
VertexLabels -> Placed["Name", Center], VertexStyle -> White,
VertexSize -> Medium, EdgeLabels -> "EdgeWeight",
ImageSize -> Large,

gdm2 = Round@GraphDistanceMatrix[g2];