SPFA算法 最短路径优先算法
用来计算一个带权连通图中两个顶点之间的最短距离,权值表示距离
算法的基本上就是一个BFS 广度优先遍历
初始开始节点的距离为0 , 入栈,其他所有顶点的距离标为无穷大
BFS开始, 出栈栈顶元素,找出邻接点,用该元素距离加上边的权值与邻接点距离比较,如果新值比较小,那么更新节点,把节点入栈
栈为空的情况下得到开始节点到图中所有节点的最短路径。
算法限制:需要图中不存在为权值和负数的环路,(PS存在的非负值环路可以做)
今天比较累就不写demo了, 如果有人需要java算法demo,评论里call我
PS最近看到好多都是以前离散数学学的 现在都忘的差不多了 真是太亏了