回溯算法实现矩阵最小权重路径-Java版本

一、问题说明

矩阵拓扑：

1 2 3 
4 5 6 
7 8 9 
最小权重：21

最小权重路径：
[0, 0] [0, 1] [0, 2] [1, 2] [2, 2] 

二、代码实现

package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BackTrace {
    private int min = Integer.MAX_VALUE;
    private int[][] list = new int[3][3];

    private List<int[]> minPath = new ArrayList<>();

    private void search(int n, int row, int column, int curr, List<int[]> path) {
        if (row == n-1 && column == n-1) {
            curr += list[row][column];
            int[] temp = {row, column};
            path.add(temp);

            if (curr < min) {
                min = curr;
                minPath = new ArrayList<>(path);
            }
            return;
        }

        path.add(new int[]{row, column});

        // right column+1
        if (column+1 < n) {
            search(n, row, column+1, curr+list[row][column], path);
        }

        // down row+1
        if (row+1 < n) {
            search(n, row+1, column, curr+list[row][column], path);
        }

        path.remove(path.size()-1);
    }

    public static void main(String[] args) {
        BackTrace backTrace = new BackTrace();
        int i = 1;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                backTrace.list[j][k] = i;
                i++;
            }
        }

        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                System.out.print(backTrace.list[j][k] + " ");
            }
            System.out.println();
        }

        List<int[]> path = new ArrayList<>();
        backTrace.search(3, 0, 0, 0, path);
        System.out.println(backTrace.min);

        for (int i1 = 0; i1 < backTrace.minPath.size(); i1++) {
            System.out.print(Arrays.toString(backTrace.minPath.get(i1)) + " ");
        }
    }
}

原文地址：https://blog.csdn.net/m0_37145844/article/details/144058175

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！