Dijkstra算法(单源最短路径)
**Dijkstra算法(单源最短路径)**
Dijkstra算法是解决**非负权图**单源最短路径问题的经典算法。它能够找到从源点到图中所有其他顶点的最短路径。下面我们分步骤详细讲解。
### 1. 问题描述
给定一个带权有向图(或无向图),图中每条边的权值均为非负数,以及一个源点(起点)。要求找出从源点到图中所有其他顶点的最短路径长度(即最短距离)。
### 2. 核心思想
Dijkstra算法采用**贪心策略**。它维护一个集合S,该集合包含已经找到最短路径的顶点。算法反复从未确定最
2025-11-10 22:25:40
0