APTX Blog

A Moe Blog Set By APTX

C/C++ 最短路算法Dijkstra算法 + 堆优化模板

文章目录[隐藏]

简介

Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

无优化复杂度:O(n ^ 2)

那么有O(km)的Spfa算法我们为什么需要Dijkstra算法呢?

因为某些毒瘤出题人会专门设计网格图来卡Spfa算法,使其变为O(m ^ 2)如下方提到的落谷题目。

洛谷:P3371(弱化版) Spfa能过    P4779(标准版)卡Spfa

普通算法

这是Dijkstra的普通算法(无优化)复杂度O(n ^ 2)

堆优化

这是Dijkstra算法的堆优化。复杂度为O(nlogn)

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注