Title: An efficient implementation for solving the all pairs minimax path problem in an undirected dense graph Show Chinese title

Title: 一种在无向稠密图中求解所有点对最小最大路径问题的高效实现

Abstract: We provide an efficient $ O(n^2) $ implementation for solving the all pairs minimax path problem or widest path problem in an undirected dense graph. It is a code implementation of the Algorithm 4 (MMJ distance by Calculation and Copy) in a previous paper. The distance matrix is also called the all points path distance (APPD). We conducted experiments to test the implementation and algorithm, compared it with several other algorithms for solving the APPD matrix. Result shows Algorithm 4 works good for solving the widest path or minimax path APPD matrix. It can drastically improve the efficiency for computing the APPD matrix. There are several theoretical outcomes which claim the APPD matrix can be solved accurately in $ O(n^2) $ . However, they are impractical because there is no code implementation of these algorithms. It seems Algorithm 4 is the first algorithm that has an actual code implementation for solving the APPD matrix of minimax path or widest path problem in $ O(n^2) $, in an undirected dense graph. Show Chinese abstract

Abstract: 我们提供了一个高效的$ O(n^2) $实现，用于求解无向密集图中的所有点对最小最大路径问题或最宽路径问题。 这是之前一篇论文中算法4（通过计算和复制得到MMJ距离）的代码实现。 距离矩阵也称为所有点路径距离（APPD）。 我们进行了实验来测试该实现和算法，并将其与其他几种求解APPD矩阵的算法进行了比较。 结果表明，算法4在求解最宽路径或最小最大路径的APPD矩阵方面表现良好。 它可以显著提高计算APPD矩阵的效率。 有几个理论成果声称APPD矩阵可以在$ O(n^2) $内准确求解。 然而，它们不实用，因为这些算法没有代码实现。 似乎算法4是第一个在无向密集图中求解最小最大路径或最宽路径问题的APPD矩阵的实际代码实现算法，在$ O(n^2) $中。