本系列旨在用简单的人话讲解算法,尽可能避免晦涩的定义,读者可以短时间内理解算法原理及应用细节。我在努力!
本篇文章编程语言为Python,供参考。
迪杰斯特拉算法(Dijkstra)
典型最短路径算法。用于计算一个节点到其他节点的最短路径。
基本原理:从起始点出发,重复寻找当前距离起始点最近的且未访问过的结点,然后利用该结点更新距离数组,直到访问过全部结点为止,最终的距离数组即为起始点到其余个点的最短路径距离。
1. 邻接矩阵构建
基本用途:用一个二维数组存放两两结点之间的距离或权值。
2. 算法实现
最终得到的距离数组的每一项就是起始点到该点的最短距离。
3. 最短路径的寻找
理论依据:
由于 距离数组 是不断更新的,所以最终 目标点索引 所对应的值一定是 起始点到目标点的最短路径距离。所以最后一次更新这个值的结点 一定是 最短路径上 目标点的上一个结点。(否则就会被更短的再次更新,就不可能是最后一次更新)
由于上一个结点一定是最短路径上的结点,所以根据最优化原理(principle of optimality),上一个结点索引 所对应的值一定是 起始点到该点的最短距离,(否则就会出现更优路径,这条路径就不可能是最短路径)。
所以,以此类推,反向推回去,一直到起始点,就得到了最短路径。
有了理论依据,再返回去看刚才的距离数组更新过程,就可以找出最短路径。
附全部源码:
#北京 天津 郑州 济南 长沙 海南# 0 1 2 3 4 5#模拟从文件中读入图的各个路径a = """0 1 5000 2 1001 2 9001 3 3002 3 4002 4 5003 4 13003 5 14004 5 1500"""INF = float('inf')#定义邻接矩阵 记录各城市之间的距离weight = [[INF if j!=i else 0 for j in range(6)] for i in range(6)]#解析数据b = [[int(i) for i in i.split(' ')] for i in a.split('\n') if i != '']for i in b:weight[i[0]][i[1]] = i[2]weight[i[1]][i[0]] = i[2]def dijkstra(src, target):"""src : 起点索引dist: 终点索引ret: 最短路径的长度"""#未到的点u = [i for i in range(6)]#距离列表dist = weight[src][:]#把起点去掉u.remove(src)#用于记录最后更新结点last_update = [src if i != INF else -1 for i in dist] while u != []:idx = 0min_dist = INF#找最近的点for i in range(6):if i in u and dist[i] < min_dist:min_dist = dist[i]idx = i#从未到列表中去掉这个点u.remove(idx)#更新dist(借助这个点连接的路径更新dist)for j in range(6):if j in u and weight[idx][j] + min_dist < dist[j]:dist[j] = weight[idx][j] + min_dist#记录更新该结点的结点编号last_update[j] = idx#输出从起点到终点的路径结点tmp = targetpath = []while tmp != src:path.append(tmp)tmp = last_update[tmp]path.append(src)print("->".join([str(i) for i in reversed(path)]))return dist[target]