算法基础：优化算法
|
学生不需要记住迪杰斯特拉最短路径算法的步骤。 |
迪杰斯特拉是一位荷兰计算机科学家，他创建了最短路径算法。据说他只花了 20 分钟就完成了。
智能手机的众多功能之一是能够快速生成不同地点之间的路线。选择标准各不相同，从最快到最短，通常包括步行、骑自行车、开车或乘坐公共交通工具。如果您偏离了原始路径，手机将在几秒钟内为您重新规划路线。一种有效找到最佳路线的方法是使用迪杰斯特拉算法。这是一个优化算法的示例。
地图上有许多相互连接的位置，从任意一个位置开始，找到到达另一个位置的最短距离。所有位置都通过中间位置连接在一起，并且任何两个连接位置之间的旅行时间是已知的。但是，并非所有位置都直接连接。
让我们通过创建一个地图的抽象来研究迪杰斯特拉的解决方案。
....... 地图图示 .......
首先，我们需要创建位置的地图。我们将位置称为节点。
....... 节点图示 ......
两个节点之间的距离（或取决于问题的行驶时间）称为顶点（复数为顶点）。
...... 节点和顶点图示 .....
首先，创建抽象，并添加如上所示的节点和标记的顶点。然后识别起点节点。识别与起点节点直接连接的每个节点，并将起点节点到该节点的距离分配给它。（这些是在下面链接示例中表示节点的圆圈中写入的数字）所有顶点都涂成绿色。绿色顶点可能是最短路线的一部分。
接下来，识别包含最小数字的节点。识别与该节点连接的节点，并计算从起点到这些新节点的顶点的总和（并在节点中写入）。如果这些节点中的一个已经具有一个比新计算的数字更大的值，则将其划掉并替换为较小的数字。已添加到节点的顶点涂成绿色。如果这些节点中的一个具有一个值，该值小于或等于新计算的数字，则忽略它。
然后重复此过程。即识别新的最小节点，识别所有直接连接的节点，并计算总距离。属于新的最短距离的顶点涂成绿色。最终，包含最小值的节点是我们试图到达的节点。其中的值是起点和终点节点之间的最短距离。
连接它们的路径是它们之间的绿色路径
此动画将帮助您了解此过程。
http://www.gitta.info/Accessibiliti/en/html/Dijkstra_learningObject2.html
虽然迪杰斯特拉算法旨在找到两点之间的最短距离，但最终网络具有从起点到网络中任何点的最短距离。
如果动画中的网络有另一个节点距离起点超过 12 个单位，则它显然不涉及最短路径，但算法将运行，直到所有可能的节点和路径都被考虑。如果此问题在导航设备中未解决，它将在找到从伦敦到伯明翰的最佳路线之前考虑苏格兰的道路。这显然是浪费时间。对迪杰斯特拉算法的简单改进是在所有未考虑的顶点等于或大于起点和所需终点之间计算的最短距离时停止。
