EAVE

Dijkstra算法详细(单源最短路径算法)

介绍

关于 dijkstra 算法,许多人或许感觉了解而又生疏,或许大部分人比较了解 bfs和dfs ,而对dijkstra和floyd算法或许知道大概是图论中的某个算法,可是或许不清楚其间的效果和原理,又或许,你从前感觉它很难,那么,这个时分正合适你重新认识它。

Dijkstra能是干啥的?

Dijkstra是用来求单源最短途径的

就拿上图来说,假设直到的途径和长度已知,那么能够运用 dijkstra 算法核算 南京到图中一切节点的最短间隔。

单源什么意思?

和 bfs 求的最短途径有什么区别?

Dijkstra在处理详细实例的使用仍是许多的,由于详细的问题其实带权更多一些。

比如一个城市有多个城镇,城镇或许有路途,也或许没有,整个城镇联通,假如想核算每个城镇到a镇的最短途径,那么Dijkstra就派上了用场。

算法剖析

关于一个算法,首先要了解它的 运转流程 。

关于一个Dijkstra算法而言,条件是它的条件条件和环境:

Dijkstra的中心思维是贪心算法的思维。不明白贪心?

贪心算法是指,在对问题求解时,总是做出在当时看来是最好的挑选。也便是说,不从全体最优上加以考虑,他所做出的是在某种意义上的部分最优解。

贪心算法不是对一切问题都能得到全体最优解,关键是贪心战略的挑选,挑选的贪心战略有必要具有无后效性,即某个状况曾经的进程不会影响今后的状况,只与当时状况有关。

关于贪心算法,在许多状况都能用到。下面举几个不恰当的比如!

打个比如,吃自助餐,方针是吃回本,那么胃有限那么每次都仅最贵的吃。

上学时,麻麻说只能带5个苹果,你想带最多,那么选五个苹果你每次都选最大的那个五次下来你就选的最重的那个。

不难发现上面的 战略 尽管没有很强的理论数学根据 ,或许不太好阐明。可是 现实规则便是那样 ,而且关于贪心问题大部分都需求 排序 ,还或许会遇到类排序。而且一个物体或许有多个特点,不同问题需求依照不同特点进行排序,操作。

那么咱们的 Dijkstra 是怎么贪心的呢?关于一个点,求图中一切点的最短途径,假如没有正确的办法胡乱想的确很难算出来,而且假如暴力匹配复杂度呈指数级上升不合适处理实际问题。

那么咱们该怎么想呢?

Dijkstra算法的条件:

简略的归纳流程为: