什么是Dijkstra算法，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。
迪杰斯特拉(Dijkstra)算法是求解“图”中单源最短路径的算法之一，所谓单源最短路径是指给定一个“初始节点”，求解其到其它各顶点的最短路径。
为了方便描述，假设图中所有边的权重都不为负：
该图已经较简洁，并且方便对该算法进行描述：
假设1号节点为指定的开始节点，现欲求1号节点到2、3、4号各节点的最短路径。其中1号到2号节点的求解过程如下：
（1）由于1号节点与2、3、4号节点直接相连的路径分别为w6、w5、w1（我们将这几个路径放到一个临时的集合中，并试图从中选择一个到其它节点中路径最短的那个）。
（2）如果临时集合中w6为其中的最短路径，则w6为最终结果，关键问题是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的路径和小于w6，那么临时集合中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为负，这样w6不一定是最短路径），这是前提条件。当然该算法在真正实现的时候还需要考虑一下权重相等的情况。
看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注亿速云行业资讯频道，感谢您对亿速云的支持。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
