词条 | 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算法 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。