一、Dijkstra 算法简介
Dijkstra(迪杰斯特拉)算法是一种单源最短路径算法,用于在带非负权重的图中,计算某个起点到其它所有顶点的最短距离。它由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出。
基本思想
Dijkstra 算法的核心思路是贪心策略:
每次从当前未访问的节点中选择距离起点最近的一个,确定它的最短路径,然后用它去更新其它节点的最短距离,直到所有节点都确定最短路径。
工作过程
假设:
- 图有VVV个顶点
- 用
dist[]数组记录起点到各顶点的最短距离 - 用
visited[]记录哪些顶点已经确定了最短路径