多源最短路

这个标题其实有歧义

从多个源点中任意一个出发

其实可以新建一个点$v$，从这个点向所有源点$s_i$建权为$0$的边，跑最短路即可

All-pairs shortest paths

常用算法为$Flody$，但今天要记录的不是这个

但是！！

用Dijkstra遍历一遍节点更快！

负权图用SPFA遍历一遍节点也比Flody快！

觉得SPFA慢，用Johnson最短路也行！

johnson全源最短路 (opens new window)