现在的位置: 首页 > 综合 > 正文

SPFA

2019年06月14日 ⁄ 综合 ⁄ 共 294字 ⁄ 字号 评论关闭

SPFA算法  最短路径优先算法

用来计算一个带权连通图中两个顶点之间的最短距离,权值表示距离

算法的基本上就是一个BFS  广度优先遍历

初始开始节点的距离为0 , 入栈,其他所有顶点的距离标为无穷大

BFS开始, 出栈栈顶元素,找出邻接点,用该元素距离加上边的权值与邻接点距离比较,如果新值比较小,那么更新节点,把节点入栈

栈为空的情况下得到开始节点到图中所有节点的最短路径。

算法限制:需要图中不存在为权值和负数的环路,(PS存在的非负值环路可以做)

今天比较累就不写demo了, 如果有人需要java算法demo,评论里call我

PS最近看到好多都是以前离散数学学的  现在都忘的差不多了 真是太亏了

抱歉!评论已关闭.