视频字幕
图是计算机科学中重要的数据结构，由顶点和边组成。顶点代表实体或对象，边表示它们之间的关系。在加权图中，每条边都有一个权值，表示连接的代价或距离。图可以是有向的，用箭头表示方向，也可以是无向的。这种结构广泛应用于网络分析、路径规划和社交网络等领域。
深度优先搜索是图遍历的重要算法。它从起始顶点开始，沿着一条路径尽可能深入探索，直到无法继续为止，然后回溯到上一个顶点继续探索其他路径。DFS使用栈结构或递归实现，能够系统地访问图中的所有顶点。在这个例子中，我们从顶点A开始，依次访问B、D，然后回溯到B，再访问C和E，完成整个图的遍历。
广度优先搜索采用逐层遍历的策略，与深度优先搜索形成鲜明对比。BFS从起始顶点开始，首先访问所有直接相邻的顶点，然后再访问这些顶点的邻接顶点。这种层次性的遍历方式使用队列数据结构实现。在这个例子中，我们从顶点A开始作为第0层，然后访问第1层的B和C，最后访问第2层的D和E。BFS特别适用于寻找最短路径和层次分析。
最短路径问题是图论中的核心问题之一。在加权图中，我们需要找到从源点到目标点的最短路径，其中路径长度等于所有边权值的总和。从源点S到目标点T可能存在多条不同的路径。比如路径1经过A和B，总长度为8；路径2直接经过C，总长度为7；路径3直接从A到T，总长度为10。通过比较可以发现，路径2是最短的。这类问题在导航、网络通信和物流等领域有广泛应用。
Dijkstra算法是解决单源最短路径问题的经典算法，由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出。该算法采用贪心策略，每次选择距离源点最近的未访问顶点进行处理。算法首先初始化距离表，将源点距离设为0，其他顶点距离设为无穷大。然后重复选择最小距离的未访问顶点，更新其邻接顶点的距离值。这个过程保证了每次确定的最短距离都是全局最优的。算法的时间复杂度为O(V²)，适用于所有边权值非负的图。