数据结构-Dijkstra算法实现-OC

前言：

一直对于最短路径算法比较好奇，适用的场景非常多，类似地铁，封闭室内，开阔的园区等场景，在给定了几个确定节点，和通路的情况下，求最短距离或者最短时间；这种应用场景是非常常见的，于是实现一下ios版本的Dijkstra算法，欢迎建议；

适用场景：旅游，交通类项目

算法方式：通过权值判断最短路径点，通过嵌套循环更新最短路径表dis[]和通了路径表father[]

特性：贪心算法，不使用负权数

例子：无向图；有向图原理一样

开始：

上货：

1.定义全局变量：地图矩阵

2.初始化全局变量值绘制矩阵参数，对照以上路线图可看明白：

3.实现dijksta算法：注意使用二维循环数组

一.外循环用于遍历所有结点，第一个子循环获取距离原点start的最短距，更新最短路径father路线表

二.第二个子循环，利用第一个子循环确定的最短路径点min_i索引与min_i节点相关点计算min_i跟索引点w距离+dis[min_i](min_i与原点start距离)，是否小于dis[w](w与原点start距离),成立则更新dis表，并重新刷新father表重新绘制最短线路.

这里就是最终获得的最短路径值，以及路线结果；

这里就是最终获得的最短路径值，以及路线结果：

总结：总体来说Dijkstra算法没有过多考虑时间复杂度问题，用到迭代思路，效率方便：算法效率不及a星算法；不过代码比较精炼，可读性较强。注重一个原理：一层大循环更新一次最短距离表和路径表，后面慢慢领悟起来就容易了。

后面会理解下a星星算法，来实现最短路径，相信也蛮有意思！欢迎大家踩点互相学习，算法枯燥，趣味无穷！