算法笔记-Dijsktra

算法笔记

Dijkstra

Dijkstra 算法

1. 每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中。
2. 计算刚加入节点A的邻近节点B的距离（不包含标记的节点）
   若（节点A的距离+节点A到节点B的边长）< 节点B的距离，就更新节点B的距离和前面点。

适用于从一个顶点出发求其余各个顶点最短路径。且各边权重不能有负数

若存在负数则需要使用Bellman-Ford算法

若想求任意两点之间的最短路径，就需要使用Floyd算法