什么是Dijkstra算法算法,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
迪杰斯特拉(迪杰斯特拉)算法是求解“图”中单源最短路径的算法之一,所谓单源最短路径是指给定一个“初始节点”,求解其到其它各顶点的最短路径。
为了方便描述,假设图中所有边的权重都不为负:
该图已经较简洁,并且方便对该算法进行描述:
假设1号节点为指定的开始节点,现欲求1号节点到2、3、4号各节点的最短路径。其中1号到2号节点的求解过程如下:
(1)由于1号节点与2、3、4号节点直接相连的路径分别为将w5, w1 <强>(我们将这几个路径放到一个临时的集合中,并试图从中选择一个到其它节点中路径最短的那个)。
(2) <强>如果临时集合中将为其中的最短路径,则将为最终结果,关键问题是w1→w4, w1→w3→w2, w5→w2, w5→w3→w4也是其余的4条路径,所以我们假设(1)中w1为与1号节点直连路径中最短的那条(因此w1为1号节点和4号节点的最短路径,我们将4号节点放入到最终的最短路径集合中)。
(3)对于4号节点,除了直连的1号节点外,还有其余的2号节点和3号节点。<强>如果w1→w4的路径和小于将那么临时集合中1号与2号节点的最短路径需更新为w1 + w4(假设更新)。同理w1→w3的路径和小于w5,则临时集合中1号与3号节点的最短路径需更新为w1 + w3(假设更新,注意我们的目标是求1号到2号节点的最短路径,但是该算法会附带着求解到其它节点的最短路径)。
(4)目前为止在临时集合中保存着1号节点分别到2号节点和3号节点的最短路径,现按照(2)的步骤从其中选择一条最短路径来,如果选择2号节点则为最终结果,如果选择3号节点则需要按照(3)的步骤进一步判断如果w1→w3→w2的路径和小于w1→w4则最终的最短路径更新为w1 + w3 + w2。
<强>注意:以上就是该算法的全过程,而且前提条件是权重不为负,那么假设权重可能为负则该算法的第(1)步就不能实现,因为一开始就不能选择一个到其它节点中路径最短的那个节点(可以假设w2为负,这样将不一定是最短路径),这是前提条件。当然该算法在真正实现的时候还需要考虑一下权重相等的情况。
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注行业资讯频道,感谢您对的支持。
