「官网地址0365.tv」-「永久地址0365.tv」

sssp是指求从源点s到其它所有点的最短路径问题。

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

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

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

三角己旬拜说形性质

设源点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算法