视频字幕
Dijkstra算法是解决单源最短路径问题的经典算法。给定一个带权重的图和起始顶点，算法能找到从起点到图中所有其他顶点的最短路径。这里我们有一个简单的图，顶点A是我们的起点，用黄色标记。算法的核心是使用优先队列来贪婪地选择当前距离起点最近的顶点进行处理。
算法的初始化步骤非常重要。首先创建距离数组，将起点A的距离设为0，其他所有顶点的距离设为无穷大。然后创建一个优先队列，用于存储距离和顶点的对。将起点A和距离0作为第一个元素加入队列。所有顶点初始时都标记为未访问状态。这样就完成了算法的初始化准备工作。
现在开始第一次迭代。从优先队列中取出距离最小的元素，也就是起点A。将A标记为已访问，用绿色表示。然后对A的所有邻居进行松弛操作。A到B的距离是4，小于B当前的无穷大距离，所以更新B的距离为4。A到D的距离是2，也小于D的无穷大距离，更新D的距离为2。最后将新的距离-顶点对加入优先队列。
继续算法的迭代过程。第二次迭代时，从队列取出距离最小的顶点D，标记为已访问。对D的邻居E进行松弛，距离2加3等于5，小于E的无穷大距离，所以更新E的距离为5。第三次迭代取出顶点B，对其邻居进行松弛。B到C的距离是7，更新C的距离。但B到E的距离是9，大于E当前的距离5，所以不更新。
算法执行完毕后，我们得到了从起点A到所有其他顶点的最短距离。A到B的最短距离是4，A到C的最短距离是6，通过路径A到D到E到C。A到D的距离是2，A到E的距离是5。黄色高亮显示的是最短路径树。Dijkstra算法的时间复杂度是O((V+E)logV)，适用于处理非负权重的图，通过贪心策略保证找到最优解。