Enumerating all geodesics

Abstract

By "geodesic" we mean any sequence of vertices $(v_1,v_2,...,v_k)$ of a graph $G$ that constitute a shortest path from $v_1$ to $v_k$. We propose a novel, natural algorithm to enumerate all geodesics of $G$, and pit it (using Mathematica) against the standard procedure for the task. The distance matrix $D(G)$ plays a crucial role in this. In fact, part of our article is devoted to survey its many uses in related tasks.

12 pages