import numpy as np
import networkx as nx

inf = float('inf')


def find_hamiltonian_cycles(distances):
    num_nodes = distances.shape[0]
    graph = nx.DiGraph()
    for i in range(num_nodes):
        for j in range(num_nodes):
            if distances[i][j] != inf:
                graph.add_edge(i, j, weight=distances[i][j])

    hamiltonian_cycles = list(nx.simple_cycles(graph))
    hamiltonian_cycles = [cycle + [cycle[0]] for cycle in hamiltonian_cycles if len(cycle) == num_nodes - 1]

    return hamiltonian_cycles


# distances = np.array([[inf, 69, 48, inf, 41, 78], [69, inf, 48, 53, 91, inf], [48, 48, inf, 19, 86, inf], [inf, 53, 19, inf, 96, 10], [41, 91, 86, 96, inf, inf], [78, inf, inf, 10, inf, inf]])
distances = np.array([[inf, 94, 67, 65, inf], [94, inf, inf, 41, inf], [67, inf, inf, inf, 65], [65, 41, inf, inf, 54], [inf, inf, 65, 54, inf]])
all_hamiltonian_cycles = find_hamiltonian_cycles(distances)

if all_hamiltonian_cycles:
    print("存在的哈密尔顿回路路径为：")
    for cycle in all_hamiltonian_cycles:
        print(cycle)
else:
    print("不存在哈密尔顿回路")