一.算法原理
1.基本原理
Dijkstra算法是利用广度优先搜索思想（BFS）的一种**单源最短路径算法**，相对于简单粗暴时间复杂度为O(n^3)的Floyed算法，（详情见我另一篇博客 [只有五行的Floyed算法及全路径输出](https://blog.csdn.net/include_IT_dog/article/details/88938561)），Dijkstra算法的时间复杂度则有好的多，为O(n^2)。 该算法以起点为中心，将相邻边加入到优先队列中，每次弹出队列中距起点最近的点，利用伸缩操作(relaxation)，更新该点各相邻节点到源点的最近距离(这里用到了贪心算法原理), 存入到一个集合disTo中，该集合中记录每一个点到源点的最近距离。 伪代码： undefined ### 2.如何保存最短路径? 在pathTo集合中，设置此节点的上一节点。如果这点没有被访问过，就加入到优先队列中，就这样重复操作层层向外遍历，最后就可以生成一个最短路径树，对于从该源点到某一点的最短路径问题，只要看该点是否被访问过，被访问过的点说明存在最短路径，回溯pathTo集合，如pathTo(A) = B, B是使A到源点距离最近的相邻点（由贪心算法可知）,pathTo(B) = C , C是使B到源点距离最近的相邻点,反复操作，直到pathTo(X) = 源点。即可得到最短路径 二.算法实现 ------ undefined ### 1.测试  输入： | edges: | n: | k: | pathTo | | --- | --- | --- | --- | | {{0, 1, 15},{0, 3, 5}, | 6 | 0 | 4 | | {1, 5, 6}, {3, 5, 20}, | | | | | {1, 2, 15}, {3, 2, 30}, | | | | | {2, 4, 10}, {5, 4, 9}}; | | | | 预计输出：最短距离：30 路径：0-->1-->5-->4 环境：windows10，java11 ### 2.结果 会了Dijkstra，不会DFS那更不得行，帮你安排了DFS的递归实现与堆栈实现
本文转载自: 掘金