分类： 算法

Johnson 和 Floyd 一样，是一种能求出无负环图上任意两点间最短路径的算法。该算法在 1977 年由 Donald B. Johnson 提出。

在 X Round 4 上做到了「尺规作图」这道非常有意思的提交答案题，后来得知这题的灵感来自于 Euclidea 这款智力游戏，于是决定体验一下。

然后就意识到自己的几何水平退化实在太厉害了…于是决定写篇博客来记录一下自己解题的心路历程。