正文
最优路径算法合集（附python源码）（原创）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
主要的最优（最短）路径算法：
一、深度优先算法；二、广度优先算法；三、Dijstra最短路径；四、floyd最短路径（待）；
一、深度优先算法
图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
无向无权值网络
data = [[0, 0, 1, 1, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1, 0]]
def depth_first_search(data, data_index): # 有向、无向都可以满足要求
d1 = [data_index[0]]
index_now = 0 for i in range(len(data_index) - 1): # 只需要再寻找剩余的数值即可
state = 1
for j in range(len(data[index_now])): # 遍历可行路径
if data[index_now][j] == 1: # 如果该路径可行，则直接判断
if data_index[j] not in d1: # 判断原始输出中是否已有
d1.append(data_index[j])# 无，则加入
index_now = j
state = 0
break
if state:
for k in d1[-2::-1]: # 到达叶子后的操作
index_now = data_index.index(k)
for j in range(len(data[index_now])): # 遍历可行路径
if data[index_now][j] == 1: # 如果该路径可行，则直接判断
if data_index[j] not in d1: # 判断原始输出中是否已有
d1.append(data_index[j]) # 无，则加入
index_now = j
break
if index_now != data_index.index(k):
break # print(d1)
return d1 if __name__ == "__main__":
data = [[0, 0, 1, 1, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1, 0]]
data_w = [[0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0]]
data_index = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# print(data_index.index('F'))
d1 = depth_first_search(data_w, data_index)
print(d1)
输入（无向图）：
data = [[0, 0, 1, 1, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1, 0]]
输出：
['A', 'C', 'B', 'D', 'F', 'G', 'E']
二、广度优先算法
广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。
它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。
def breadth_first_search(data, data_index): # 无向图、有向图都可以的
d1 = [data_index[0]]
index_now = [0]
while len(d1) != len(data_index):
index_mid = []
for i in index_now: # i 为当前 父节点
for j in range(len(data[i])): # 查询父节点的子节点
if data[i][j] == 1:
if data_index[j] not in d1:
d1.append(data_index[j])
index_mid.append(j)
index_now = index_mid
print(d1)
return d1 if __name__ == "__main__":
data = [[0, 0, 1, 1, 0, 1, 0], [0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1, 0]]
data_w = [[0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0]]
data_index = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# print(data_index.index('F'))
d1 = breadth_first_search(data_w, data_index)
# print(d1)
输入（有向图）：
data_w = [[0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0, 0]]
输出：
['A', 'B', 'C', 'E', 'F', 'D', 'G']
三、Dijstra最短路径（迪杰斯特拉算法）
参考视频：https://www.bilibili.com/video/av25829980?from=search&seid=7854146334299589449
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
OSPF 协议 ：Open Shortest Path First开放式最短路径优先，底层是迪杰斯特拉算法，是链路状态路由选择协议，它选择路由的度量标准是带宽，延迟。
def priority_queue(data, d0): # 自建优先队列格式
state = 1
for i in range(len(data)):
if d0[1] < data[i][1]:
data.insert(i, d0)
state = 0
break
if state:
data.append(d0)
return data def dijkstra_search(data, data_index, index):
parent = {} # 字典映射，更新前级节点
queue = [] # 优先队列
queue_out = [[data_index[index], data[index][index], 0]] # 输出队列 while len(queue_out) < len(data_index):
root_node = data_index.index(queue_out[-1][0]) # 当前最优节点
# print(root_node)
for i in range(len(data_index)): # 遍历所有的可能性
if data[root_node][i] != -1: # 检查是否可直连，是
if data_index[i] not in [x[0] for x in queue_out]:
queue = priority_queue(queue,
[data_index[i], data[root_node][i] + queue_out[-1][1], queue_out[-1][0]])
# print(queue) # 检查优先队列的情况 [['C', 1], ['B', 5]] for i in range(len(queue)): # 0,1
# print(queue[i][0])
if queue[i][0] not in [x[0] for x in queue_out]:
parent[queue[i][0]] = queue[i][-1]
queue_out.append(queue[i])
del queue[i]
break # print(queue)
# print('queue_out',queue_out)
return queue_out, parent if __name__ == "__main__": data_weight = [[0, 5, 1, -1, -1, -1], [5, 0, 2, 1, -1, -1], [1, 2, 0, 4, 8, -1], [-1, 1, 4, 0, 3, 6],
[-1, -1, 8, 3, 0, -1], [-1, -1, -1, 6, -1, -1]]
data_index = ['A', 'B', 'C', 'D', 'E', 'F']
# print(data_index.index('F'))
d1, d2 = dijkstra_search(data_weight, data_index, 3)
print(d1)
print(d2) target = 'A'
for i in d1:
if i[0] == target:
print('路径最短距离为：', i[1]) key = target
d3 = [target]
while key in d2.keys():
d3.insert(0, d2[key])
key = d2[key]
print('最优路线为：', d3)
输入：
data_weight = [[0, 5, 1, -1, -1, -1], [5, 0, 2, 1, -1, -1], [1, 2, 0, 4, 8, -1], [-1, 1, 4, 0, 3, 6], [-1, -1, 8, 3, 0, -1], [-1, -1, -1, 6, -1, -1]]
data_index = ['A', 'B', 'C', 'D', 'E', 'F']
d1, d2 = dijkstra_search(data_weight, data_index, 0)
输出：
路径最短距离为： 10
最优路线为： ['A', 'C', 'B', 'D', 'F']
四、floyd最短路径
！！！还没看这个算法！！！
