python利用kruskal求解最短路径的问题

93 阅读 0 评论 62 点赞

我是靠谱客的博主无私樱桃，最近开发中收集的这篇文章主要介绍python利用kruskal求解最短路径的问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

python利用kruskal算法求解最短路径的问题，修改参数后可以直接使用

 1 def kruskal():
 2
"""
 3 
kruskal 算法
 4
"""
 5
dimensional = get_array(9999) # 获取数组
 6
node_num = len(dimensional)
 7
res = []
 8
count = 0
 9
# 获取节点值
10
for i in range(node_num):
11
for j in range(i):
12
if 0 < dimensional[i][j] < 9999:
13
count += 1
14
# 临界值判断
15
if node_num <= 0 or count < node_num - 1:
16
return res
17
res = []
18
selected_node = [0]
19
candidate_node = [i for i in range(1, node_num)]
20
# 终止条件判断
21
while len(candidate_node) > 0:
22
begin, end, min_weight = 0, 0, 9999
23
for i in selected_node:
24
for j in candidate_node:
25
if dimensional[i][j] < min_weight:
26
min_weight = dimensional[i][j]
27
begin = i
28
end = j
29 
res.append([begin, end, min_weight])
30 
selected_node.append(end)
31 
candidate_node.remove(end)
32
return res