求教SPFA算法是什么?麻烦从基础讲起,关于SPFA我只知道是求最短路的.

答案:2 悬赏:30 手机版

解决时间 2021-02-03 08:28

提问者网友：我是女神我骄傲
2021-02-03 01:03

最佳答案

五星知识达人网友：从此江山别
2021-02-03 02:41

首先了解下最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径. 算法具体的形式包括：确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题. 简单说你从你家到学校,有很多路,你希望走的距离最近,那你可能要过天桥,转小巷,最后找最短的以后都走那条路. 最常的算法有很多：用于解决最短路径问题的算法被称做“最短路径算法”, 有时被简称作“路径算法”. 最常用的路径算法有： Dijkstra算法 A*算法 SPFA算法 Bellman-Ford算法 Floyd-Warshall算法 Johnson算法上面了解了. 求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm. SPFA算法是西南交通大学段凡丁于1994年发表的. 我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G.我们采取的方法是松弛：设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾.这样不断从队列中取出结点来进行松弛操作,直至队列空为止. 要去找到数组邻接表先进先出队列的知识. 然后可以去看看不同语言如何写出程序. 知识是很多的每句话哪点不懂就去查懂说实话我也不懂哈哈在实际应用中我个人觉得汽车导航中如果找路肯定有涉及到采纳哦

全部回答

1楼网友：孤独的牧羊人
2021-02-03 03:04

收益了

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！