第1个回答 2022-06-07
Dijkstra（ 迪科斯特拉 ）算法是用来解决单源最短路径的算法，要求路径权值非负数。该算法利用了深度优先搜索和贪心的算法。
下面是一个有权图，求从A到各个节点的最短路径。
第1步：从A点出发，判断每个点到A点的路径（如果该点不能直连A点则距离值为无穷大，如果该点能和A直连则是当前的权值），计算完之后把A点上色，结果如下图:
第2步：从除A点之外的点查找到距离A点最近的点C，从C点出发查找其邻近的节点（除去已上色的点），并重新计算C点的邻近点距离A点的值，如图中B点，若新值（C点到A点的值+C点到该点的路径）小于原值，则将值更新为5，同理更新D、E点。同时将C标记为已经处理过，如图所示涂色。
第3步：从上色的节点中查找距离A最近的B点，重复第3步操作。
第4步： 重复第3步，2步，直到所有的节点都上色。
最后就算出了从A点到所有点的最短距离。
leetcode 743题