算法介绍
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
当然目前也有人将它用来处理物流方面，以获取代价最小的运送方案。
算法思路
Dijkstra算法采用的是一种贪心的策略。
1.首先，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T。
2.其次，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
3.从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点。
4.再次，看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
5.最后，从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点（可以到达的）。
算法图形演示
现在有图如下：
image.png
每个线的权重以及标识如图所示。
第一步：
建立dis数组和T数组。
首先从起点A 开始，将A可以直接到达的顶点的权重记录在dis数组中，无法直达的记录无穷大（当前使用FFFF表示无穷大）。
image.png
将当前选择的顶点加入数组T:
image.png
第二步：
从dis数组中选择一个不在T数组中的顶点的最小权重值的顶点，当前选择为B顶点，并将B可以直接到达的顶点的相关权重和当前dis中的权重值比较，如果当前dis权重值大，则替换：
11345863-f507be1536f1afe8.png
将B加入数组T:
image.png
第三步：
依次选择顶点C：
image.png
将C加入数组T:
image.png
第四步：
依次选择顶点D：
image.png
将D加入数组T:
image.png
第五步：
依次选择顶点E：
image.png
将E加入数组T:
image.png
第六步：
依次选择顶点F：
image.png
将F加入数组T:
image.png
因为所有的顶点都已经在T数组中了，算法结束。
这样就求得了从A点到各个顶点的最优解。
可以看到A顶点无法直达F顶点。
代码表示：
(代码中使用999代表FFF)
#encoding:utf-8
import copy
"""
图的表示方式
邻接矩阵
999代表无限远
"""
tuG=[[0, 10, 20, 999, 999, 999],
[999, 0, 999, 20, 70, 999],
[999, 999, 0, 50, 30, 999],
[999, 999, 999, 0, 999, 999],
[999, 999, 999, 10, 0, 999],
[999, 999, 999, 20, 20, 0]];
tuX = 6;
# 设置原点到其他定点的各个距离
dis = copy.deepcopy(tuG[0]);
def Dijkstra(G,v0):
"""
使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离
INF 为设定的无限远距离值
"""
t = [];
minv = v0;
while len(t) <= tuX:
t.append(minv);
#以当前点的中心向外扩散
for w in range(0, tuX):
if dis[minv] + G[minv][w] < dis[w]:
dis[w] = dis[minv] + G[minv][w]
tmp = 1000;
for i in range(0, tuX):
tmpFlag = False;
for j in range(0, len(t)):
if i == t[j]:
tmpFlag = True;
break;
if tmpFlag == True:
continue;
if tmp > dis[i]:
tmp = dis[i];
minv = i;
if __name__ == '__main__':
Dijkstra(tuG,0);
print dis;
网友评论