用java实现Hamilton最短路径

哈密顿回路是一种经过图中每个节点一次且仅一次的回路。哈密顿回路问题是一个NP完全问题，因此没有已知的多项式时间算法可以解决这个问题。不过，可以使用启发式算法来解决近似的问题。

下面是一个使用Java实现的近似算法：

import java.util.*;

public class HamiltonianPath {
    private static int[][] graph; // 图
    private static int[] path; // 存储路径
    private static boolean[] visited; // 标记是否访问过
    private static int n; // 节点数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        graph = new int[n][n];
        path = new int[n];
        visited = new boolean[n];

        // 构建图
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // 从第一个节点出发
        path[0] = 0;
        visited[0] = true;

        if(findHamiltonianPath(1)) {
            // 打印路径
            for(int i = 0; i < n; i++) {
                System.out.print(path[i] + " ");
            }
        } else {
            System.out.println("No Hamiltonian Path exists");
        }
    }

    // 查找哈密顿路径
    private static boolean findHamiltonianPath(int pos) {
        // 如果已经遍历完所有节点
        if(pos == n) {
            // 判断最后一个节点是否与第一个节点相邻
            if(graph[path[pos - 1]][path[0]] == 1) {
                return true;
            } else {
                return false;
            }
        }

        // 遍历其它节点
        for(int i = 1; i < n; i++) {
            if(isValid(i, pos)) {
                path[pos] = i;
                visited[i] = true;

                if(findHamiltonianPath(pos + 1)) {
                    return true;
                }

                // 回溯
                visited[i] = false;
            }
        }

        return false;
    }

    // 判断节点是否可达
    private static boolean isValid(int node, int pos) {
        // 如果节点已经被访问过，返回false
        if(visited[node]) {
            return false;
        }

        // 如果前一个节点与当前节点不相邻，返回false
        if(graph[path[pos - 1]][node] == 0) {
            return false;
        }

        return true;
    }
}

在这个算法中，我们使用了回溯的方法来查找哈密顿路径。我们从第一个节点开始，依次尝试访问其它节点，直到找到一条哈密顿路径或者遍历完所有节点。在查找过程中，我们使用visited数组来标记节点是否已经被访问过，使用path数组来存储路径。isValid方法用来判断节点是否可达。