<强>算法介绍
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
当然目前也有人将它用来处理物流方面,以获取代价最小的运送方案。
<强>算法思路
Dijkstra算法算法采用的是一种贪心的策略。
1。首先,声明一个数组说来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合t
2.其次,原点年代的路径权重被赋为0 (dis [s]=0)。若对于顶点年代存在能直接到达的边(s, m),则把说[m]设为w (s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点。
3.从说数组选择最小值,则该值就是源点年代到该值对应的顶点的最短路径,并且把该点加入到T中,此时完成一个顶点。
4.再次,看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在冥府中的值。
5 .最后,从冥府中找出最小值,重复上述动作,直到T中包含了图的所有顶点(可以到达的)。
<强>算法图形演示
现在有图如下:
每个线的权重以及标识如图所示。
建立说数组和T数组。
首先从起点一开始,将一个可以直接到达的顶点的权重记录在说数组中,无法直达的记录无穷大(当前使用飞行符表示无穷大)。
将当前选择的顶点加入数组T:
从dis数组中选择一个不在T数组中的顶点的最小权重值的顶点,当前选择为B顶点,并将B可以直接到达的顶点的相关权重和当前说中的权重值比较,如果当前说权重值大,则替换:
将B加入数组T:
<强>
依次选择顶点C:
将C加入数组T:
依次选择顶点D:
将D加入数组T:
依次选择顶点E:
将E加入数组T:
依次选择顶点F:
将F加入数组T:
因为所有的顶点都已经在T数组中了,算法结束。
这样就求得了从一个点到各个顶点的最优解。
可以看到一顶点无法直达F顶点。
<强>代码表示:
(代码中使用999代表FFF)
