# Vertex Order of Graph

Given a graph, I want to find the shortest distance between each pair of vertices:

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


This is what the graph looks like: It is obvious that the distance of shortest path from 1 to 6 is 3. However, when I compute the shortest distance in this way:

m = GraphDistanceMatrix[g];
m[[1, 6]]


The output is

2


It tells that the distance from 1 to 6 is 2. This is incorrect. I noticed from its documentation that "the vertices are assumed to be in the order given by VertexList[g]".

So, I called VertexList[g]:

VertexList[g]


And this is the vertex order:

{4, 5, 2, 3, 6, 1}


This actually gives troubles to my application. Is there a way to get the shortest distance according to the numerical order rather than vertex order?

GraphDistance[g, 1, 6]


returns 3.

I've had this problem in the past, and if you want to fix your original method, you can use Sjoerd C. de Vries's answer there. It's one of the few really annoying behaviours of Mathematica I've come across.

Example with a shuffled list of vertices, eleven vertices and ten edges:

edges = UndirectedEdge @@@ RandomInteger[10, {10, 2}];
g = Graph[RandomSample[Range, 10], edges, VertexLabels -> "Name"];

ClearAll[state, label]
MapIndexed[(state[#1] = #2[]) &, VertexList[g]];
MapIndexed[(label[#2[]] = #1) &, VertexList[g]];

mat = GraphDistanceMatrix[g];

mat[[state, state]]


This is still lightning-fast for ten thousand edges on a hundred vertices for me.

Alternatively, you may ensure the vertex list is ordered when you create the graph, by using the Graph[vertexlist, edgelist] construction. If the vertex list is Range[n] for some n, the following will work to find the distance between vertices of name 4 and 10 (but might forget any metadata you've stored in the graph):

orderedg = Graph[Sort@VertexList[g], EdgeList[g]]
GraphDistanceMatrix[orderedg][[4, 10]]

• This is okay for computing a pair, but too slow for all pairs shortest distance. Aug 23, 2015 at 9:02
• @Purboo, how big is your graph? Aug 23, 2015 at 9:03
• about 100 vertices and 10000 undirected edges. Aug 23, 2015 at 9:05
• Does Sjoerd C de Vries's answer not work quickly? I'll edit into this post. Aug 23, 2015 at 9:08
• @Purboo Added to post. Aug 23, 2015 at 9:12