# 迪杰斯特拉路径

> 计算图中从起点到所有其他节点最短路径的经典算法。

- ID: m12448
- 分类: technical
- 领域: 算法

## 定义

计算图中从起点到所有其他节点最短路径的经典算法。贪心策略，每次选择当前距离最短的未访问节点。脚手架作用：最优子结构的力量。最短路径的子路径也是最短路径——这个性质使得问题可被分解。

## 机制

在非负权图中用贪心加优先队列求单源最短路径，逐步锁定最短距离。

## 练习

初始化起点距离为0，反复取最小未定节点松弛其邻边。

## 脚手架用法

最优子结构的力量。最短路径的子路径也是最短路径——这个性质使得问题可被分解。

[阅读网页](https://thinkingmodels.site/entries/detail/m12448)