有一个6行6列的二维数组数组的值代表 经过当前节点需要花费的时间给定起始节点和结束节点求两个节点之间的最短时间以及路径。 Java实现

以下是Java实现代码：

public class ShortestPath {
    private int[][] graph; // 二维数组表示图
    private int rows; // 行数
    private int cols; // 列数

    public ShortestPath(int[][] graph) {
        this.graph = graph;
        this.rows = graph.length;
        this.cols = graph[0].length;
    }

    public int getShortestTime(int startRow, int startCol, int endRow, int endCol) {
        // 初始化距离矩阵和路径矩阵
        int[][] distance = new int[rows][cols];
        boolean[][] visited = new boolean[rows][cols];
        int[][] path = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                distance[i][j] = Integer.MAX_VALUE;
                visited[i][j] = false;
                path[i][j] = -1;
            }
        }

        // 设置起点的距离为0
        distance[startRow][startCol] = 0;

        // Dijkstra算法
        for (int k = 0; k < rows * cols; k++) {
            // 找到未访问过的距离最小的节点
            int minDistance = Integer.MAX_VALUE;
            int minRow = -1;
            int minCol = -1;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (!visited[i][j] && distance[i][j] < minDistance) {
                        minDistance = distance[i][j];
                        minRow = i;
                        minCol = j;
                    }
                }
            }

            // 如果没有可达的节点了，退出循环
            if (minRow == -1 || minCol == -1) {
                break;
            }

            // 标记该节点为已访问
            visited[minRow][minCol] = true;

            // 更新该节点的邻居节点的距离和路径
            int[] neighborRows = {minRow - 1, minRow, minRow + 1, minRow};
            int[] neighborCols = {minCol, minCol + 1, minCol, minCol - 1};
            for (int i = 0; i < 4; i++) {
                int neighborRow = neighborRows[i];
                int neighborCol = neighborCols[i];
                if (neighborRow >= 0 && neighborRow < rows && neighborCol >= 0 && neighborCol < cols
                        && !visited[neighborRow][neighborCol]) {
                    int newDistance = distance[minRow][minCol] + graph[neighborRow][neighborCol];
                    if (newDistance < distance[neighborRow][neighborCol]) {
                        distance[neighborRow][neighborCol] = newDistance;
                        path[neighborRow][neighborCol] = minRow * cols + minCol;
                    }
                }
            }
        }

        // 获取最短时间和路径
        int shortestTime = distance[endRow][endCol];
        List<Integer> shortestPath = new ArrayList<>();
        int node = endRow * cols + endCol;
        while (node != -1) {
            shortestPath.add(0, node);
            node = path[node / cols][node % cols];
        }

        // 打印路径
        for (int i = 0; i < shortestPath.size(); i++) {
            int row = shortestPath.get(i) / cols;
            int col = shortestPath.get(i) % cols;
            System.out.print("(" + row + "," + col + ")");
            if (i != shortestPath.size() - 1) {
                System.out.print(" -> ");
            }
        }
        System.out.println();

        return shortestTime;
    }

    public static void main(String[] args) {
        int[][] graph = {
                {2, 3, 1, 4, 5, 2},
                {4, 2, 5, 1, 3, 2},
                {1, 6, 2, 4, 2, 3},
                {3, 4, 2, 1, 2, 4},
                {2, 5, 1, 3, 2, 4},
                {2, 2, 3, 4, 1, 2}
        };
        ShortestPath shortestPath = new ShortestPath(graph);
        int shortestTime = shortestPath.getShortestTime(0, 0, 5, 5);
        System.out.println("Shortest time: " + shortestTime);
    }
}

在上述代码中，我们使用了Dijkstra算法来计算最短路径。该算法的时间复杂度为O(n^2)，其中n为节点数。在本题中，节点数为6x6=36，因此时间复杂度为O(36^2)=O(1296)