迪杰斯特拉算法的思想是什么？
订阅
迪杰斯特拉算法按路径长度递增次序产生算法。将顶点集合V分成两组：S（已求出的顶点的集合，初始时只含有源点V0）和V-S=T（尚未确定的顶点集合）。将T中顶点按递增的次序加入到S中，保证从源点V0到S中
迪杰斯特拉算法按路径长度递增次序产生算法。将顶点集合V分成两组：S（已求出的顶点的集合，初始时只含有源点V0）和V-S=T（尚未确定的顶点集合）。将T中顶点按递增的次序加入到S中，保证从源点V0到S中其他顶点的长度都不大于从V0到T中任何顶点的最短路径长度，并且每个顶点对应一个距离值。S中顶点表示从V0到此顶点的长度，T中顶点表示从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。求最短路径的步骤包括：初始时令S={V0}，T=V-S（其余顶点），选取与S中顶点有关联边且权值最小的顶点W加入到S中，对其余T中顶点的距离值进行修改，重复上述步骤直到S中包含所有顶点。
免责声明：本内容来源于第三方作者授权、网友推荐或互联网整理，旨在为广大用户提供学习与参考之用。所有文本和图片版权归原创网站或作者本人所有，其观点并不代表本站立场。如有任何版权侵犯或转载不当之情况，请您通过400-62-96871或关注我们的公众号与我们取得联系，我们将尽快进行相关处理与修改。感谢您的理解与支持！
阅读全文
请先 登录后发表评论 ~