1
$\begingroup$

Graph

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"]
WAdj=WeightedAdjacencyMatrix[G]
GraphDistanceMatrix[G] // MatrixForm

This is part of the result of GraphDistanceMatrix:

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?

$\endgroup$
  • $\begingroup$ what does VertexList[G] give? $\endgroup$ – kglr Jun 9 at 5:35
  • $\begingroup$ {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. $\endgroup$ – Mertin Jun 9 at 6:11
  • 1
    $\begingroup$ 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. $\endgroup$ – kglr Jun 9 at 6:40
0
$\begingroup$

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]

enter image description here

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}]]

enter image description here

As stated GraphDistanceMatrix >> Details and Options

enter image description here

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}], 
 TableHeadings -> {VertexList[g1], VertexList[g1]}]

enter image description here

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}], 
 TableHeadings -> {Sort@VertexList[g1], Sort@VertexList[g1]}]

enter image description here

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, 
  VertexCoordinates -> Thread[VertexList[g1] -> GraphEmbedding[g1]]]

enter image description here

gdm2 = Round@GraphDistanceMatrix[g2];

MatrixForm[MapAt[Style[#, Blue, Bold] &, gdm2, {5, 1}], 
 TableHeadings -> {VertexList[g2], VertexList[g2]}]

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ awesome thanks so much! $\endgroup$ – Mertin Jun 9 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.