How does the FindShortestPath function handle situations with multiple paths and how does this affect the BetweennessCentrality function?

Question

I'm using the FindShortestPath function and am curious to know how Mathematica determines the shortest path when multiple such paths exist.

Here's what I have:

A = {{0, 1, 1, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 1, 1, 0}}
G = AdjacencyGraph[A, VertexLabels -> "Name"]

FindShortestPath[G, 1, 4]

The output is {1,2,4}. However, {1,3,4} is also valid. How does Mathematica choose? According to the order of the entries, 1,2,3,4?

Also, how is BetweennessCentrality handled in such cases? For example,

BetweennessCentrality[G]

yields {0,.5,.5,0}. The zeros are obvious. However, (2) falls one of the two shortest paths from (1) to (4). Do we count it as contributing 1/2 to the BetweennessCentrality of (2), or is there a normalization constant I'm missing?

Answer 1

Re the second part of the question:

BetweennessCentrality >> Details:

• BetweennessCentrality for a vertex $i$ in a connected graph is given by $\sum _ {s,t\in v\land s \neq i\land t \neq i}\frac{n_ {s,t}^i}{n_{s,t}}$, where $n_{s,t}$ is the number of shortest paths from $s$ to $t$ and $n_ {s,t}^i$ is the number of shortest paths from $s$ to $t$ passing through $ i$.

To find all paths between vertices 1 and 4 you can use FindPath:

FindPath[G, 1, 4, {GraphDistance[G, 1, 4]}, All]

{{1, 3, 4}, {1, 2, 4}}

Re: How does Mathematica choose? According to the order of the entries, 1,2,3,4?

Your guess that the path among multiple shortest paths is selected based on VertexIndexes is supported by the following small experiment:

G2 = AdjacencyGraph[{a, c, b, d},A, VertexLabels -> "Name"] 
FindShortestPath[G2, a, d]

{a, c, d}

G3 = AdjacencyGraph[{a, z, w, d},A, VertexLabels -> "Name"] 
FindShortestPath[G3, a, d]

{a, z, d}