# APSP (All-Pairs Shortest Paths (APSP))

## Description

The shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

## Parameters

$n$: number of vertices

$m$: number of edges

## Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Shimbel Algorithm 1953 $O(n^{4})$ $O(n^{2})$ Exact Deterministic Time
Floyd–Warshall algorithm 1962 $O(n^{3})$ $O(n^{2})$ Exact Deterministic Time
Seidel's algorithm 1995 $O (n^{2.{37}3} \log n)$ $O(n^{2})$ Exact Deterministic Time
Williams 2014 $O(n^{3} /{2}^{(\log n)^{0.5}})$ $O(n^{2})$ Exact Deterministic Time
Pettie & Ramachandran 2002 $O(mn \log \alpha(m,n))$ Exact Deterministic Time
Thorup 1999 $O(mn)$ $O(mn)$ Exact Deterministic Time & Space
Chan (Geometrically Weighted) 2009 $O(n^{2.{84}4})$ $O(l n^{2})$ Exact Deterministic Time
Chan 2009 $O(n^{3} \log^{3} \log n / \log^{2} n)$ $O(n^{2})$ Exact Deterministic Time