You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
46 lines
1.2 KiB
46 lines
1.2 KiB
11 months ago
|
# -*- coding: utf-8 -*-
|
||
|
|
# Time : 2023/11/3 17:42
|
||
|
|
# Author : lirunsheng
|
||
|
|
# User : l'r's
|
||
|
|
# Software: PyCharm
|
||
|
|
# File : Prin.py
|
||
|
|
|
||
|
|
import numpy as np
|
||
|
|
|
||
|
|
|
||
|
|
def prim_exists_path(distances):
|
||
|
|
num_cities = distances.shape[0]
|
||
|
|
visited = set()
|
||
|
|
pq = []
|
||
|
|
start_node = 0
|
||
|
|
|
||
|
|
visited.add(start_node)
|
||
|
|
for neighbor in range(num_cities):
|
||
|
|
if neighbor != start_node and np.isfinite(distances[start_node, neighbor]):
|
||
|
|
pq.append((distances[start_node, neighbor], start_node, neighbor))
|
||
|
|
|
||
|
|
pq.sort(key=lambda x: x[0])
|
||
|
|
|
||
|
|
while pq:
|
||
|
|
weight, node1, node2 = pq.pop(0)
|
||
|
|
if node2 not in visited:
|
||
|
|
visited.add(node2)
|
||
|
|
for neighbor in range(num_cities):
|
||
|
|
if neighbor != node2 and np.isfinite(distances[node2, neighbor]):
|
||
|
|
pq.append((distances[node2, neighbor], node2, neighbor))
|
||
|
|
|
||
|
|
pq.sort(key=lambda x: x[0])
|
||
|
|
|
||
|
|
return len(visited) == num_cities
|
||
|
|
|
||
|
|
|
||
|
|
distances = np.array([
|
||
|
|
[np.inf, 50, 99, np.inf, 64, np.inf],
|
||
|
|
[50, np.inf, 12, 45, 74, 13],
|
||
|
|
[99, 12, np.inf, 25, np.inf, 61],
|
||
|
|
[np.inf, 45, 25, np.inf, 45, 47],
|
||
|
|
[64, 74, np.inf, 45, np.inf, np.inf],
|
||
|
|
[np.inf, 13, 61, 47, np.inf, np.inf]
|
||
|
|
])
|
||
|
|
|
||
|
|
print(prim_exists_path(distances))
|