sssp

sssp是日本初代奥特曼时期的防卫队（科学特搜队）本部，这个防卫队在TV版没有全名，直到《苏醒吧！奥特曼》里才有全名。单源最短路径（SSSP）定义：

最短路径：对在权图G=(V,E),从一个源点s到汇点t有很多路径，其中路径上权和最少的路径，称从s到t的最短路径。

简单讲：找出连接两个给定点的最低成本路径

单源最短路径问题：求从源点s到其它所有点的最短路径问题，即SSSP。

令人惊讶的是，“单源单汇”与“单源多汇”两个问题的算法复杂度是一样的，有向、无向图也一样。统称单源最短路径问题。

n属性：

三角形性质

设源点s到点x、y的最短路径长度为dis[x]、dis[y]。x与y之间的距离是len[x][y]，则有下面的“三角形定理”：

dis[x] + len[x][y] >= dis[y]

松弛

若在处理过程中，有两点x、y出现不符合“三角形定理”，则可改进一下—松弛：

if ( dis[x]+len[x][y] < dis[y] )

dis[y] = dis[x]+len[x][y];

常用最短路径算法：

Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法