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

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?

• As for betweenness, reading up on the definition will answer the question. As for the shortest path, do not assume that there is any connection between the implementations of BetweennessCentrality and FindShortestPath. Also, it is not safe to make any assumptions about which path is returned—what if the implementation changes in the next version? Aug 6, 2018 at 9:27
• To understand how the decision might be made, I suggest you look at the usual algorithms for finding shortest paths. For the unweighted case, it can be done with a breadth first search. Think about how you'd implement a BFS, and how various implementation choices may impact which path is found. This should clarify things. Aug 6, 2018 at 9:27

Re the second part of the question:

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