视频字幕
Dijkstra算法是计算机科学中的经典算法，用于寻找加权图中从单个源点到所有其他顶点的最短路径。该算法采用贪心策略，每次选择当前距离最小的未访问节点进行处理。算法要求图中所有边的权重都为非负数。让我们通过一个具体的例子来理解这个算法的工作原理。
现在开始初始化Dijkstra算法。首先选择节点A作为源节点，将其距离设置为0，其他所有节点的距离初始化为无穷大。我们用红色高亮显示源节点A。创建距离表记录每个节点的当前最短距离。初始时，未访问集合包含所有节点，已访问集合为空。这个初始化过程为后续的迭代计算奠定了基础。
Dijkstra算法是计算机科学中的经典算法，由荷兰计算机科学家Dijkstra在1956年提出。它用于寻找带权图中从单个源点到所有其他节点的最短路径。算法采用贪心策略，每次选择距离最小的未访问节点进行处理，保证找到的路径是最优的。
首先进行算法初始化。我们有一个包含5个节点的带权图，节点A到E，边上的数字表示权重。初始化时，将所有节点的距离设置为无穷大，除了起始节点A设置为0。用红色圆圈标记起始节点A，其他节点用白色表示。右侧的距离表显示了当前各节点的距离值。
开始第一次迭代。从未访问的节点中选择距离最小的节点A，距离为0。将A标记为已访问，用绿色表示。现在对A的所有邻居节点进行松弛操作。A到B的距离是0加4等于4，小于B的当前距离无穷大，所以更新B的距离为4。A到D的距离是0加2等于2，小于D的当前距离无穷大，所以更新D的距离为2。用红色高亮显示被松弛的边，用蓝色表示距离被更新的节点。
进行第二次迭代。在未访问的节点中，D的距离最小为2，所以选择D进行处理。将D标记为已访问，用绿色表示。D只有一个邻居节点E，进行松弛操作：D到E的距离是2加3等于5，小于E的当前距离无穷大，所以更新E的距离为5。用红色高亮显示被松弛的边DE，用蓝色表示距离被更新的节点E。
算法继续执行直到所有节点都被访问。最终得到从起始节点A到所有其他节点的最短距离：A到A距离为0，A到B距离为4，A到C距离为6，A到D距离为2，A到E距离为5。红色边表示最短路径树。Dijkstra算法通过贪心策略，每次选择距离最小的未访问节点，保证找到的都是最优路径。这就是Dijkstra算法的完整执行过程。
继续执行算法的第三和第四次迭代。第三次选择距离最小的未访问节点B，距离为4。对B的邻居进行松弛：B到C的距离是4加3等于7，小于C的当前距离无穷大，更新C为7；B到E的距离是4加5等于9，大于E的当前距离5，所以不更新。第四次选择节点E，距离为5。E到C的距离是5加1等于6，小于C的当前距离7，所以将C的距离更新为6。红色边表示最优路径，橙色边表示被替换的路径。
最后处理节点C，算法完成。所有节点都已访问，得到从起始节点A到所有其他节点的最短距离。A到A距离为0，A到B距离为4，A到C距离为6通过路径A到D到E到C，A到D距离为2，A到E距离为5通过路径A到D到E。红色边表示最短路径树，黄色箭头显示到节点C的最短路径。Dijkstra算法通过贪心策略和松弛操作，成功找到了单源最短路径，这就是算法的完整执行过程。