[Math] Shortest Distance between all pairs of nodes in graph

Question

As the title says, how should I go about finding the shortest distance between all pairs of nodes (Each node has x and y co-odrinates associated with it) on a graph?

A brute force method is to run shortest path finding algorithms between all the pairs of the points. Is there a better way to approach this problem. (The reason I need this is I am trying to solve Traveling Salesman Problem using Ant Colony Optimziation which requires the cost matrix between each pair of nodes)

Answer 1

There are several algorithms, differing in the nature of the edge type, edge cost, and running time. Assume a graph $G$ with vertices, $V$, and edge, $E$. You do not say if your graph is directed or undirected. You do not describe edge weights. You do not indicate an expected number of edges in terms of vertices or number of vertices in terms of edges, so identifying a "best" algorithm is impossible.

Used in asymptotic estimates below, "$V$" and "$E$" denote the number of vertices and number of edges, respectively.

For undirected graphs with positive real edge weights:

• The Floyd-Warshall algorithm has $O(V^3)$ runtime.
• Pettie & Ramachandran has $O(EV \ln \alpha(E,V))$ run time, where $\alpha$ is Tarjan's inverse Ackermann function.

For undirected graphs with nonnegative integer edge weights:

• Williams has $O\left(V^3 / 2^{\Omega(\ln V)^{1/2}} \right)$ run time, where $\Omega$ is Knuth's big omega notation.
• Thorup, iterated over each vertex, has $O(EV)$ run time.

For undirected graphs having weights $1$ (for present edges) and $\infty$ (for absent edges),

• Seidel's algorithm is $O(V^\omega \ln V)$, where $\omega$ is the exponent in square matrix multiplication. It is known $\omega < 2.373$.

For directed graphs with real weights and no negative cycles,

• The Floyd-Warshall algorithm (mentioned above) has run time $O(V^3)$.
• Johnson's algorithm followed by Dijkstra's algorithm has run time $O(EV+V^2 \ln V)$.
• Pettie has run time $O(EV + V^2 \ln \ln V)$.

For directed graphs with nonnegative integer weights,

• Williams algorithm, described above can be applied.
• Hagerup has run time $O(EV + V^2 \ln ln V)$.