2 datou123789 datou123789 于 2016.09.18 08:17 提问

Java求最短路径的问题

请设计一段程序,读取各国两两之间的距离,距离以邻接矩阵表示,并计算出遍历各国的最短路径长度。
输入:国家数量n 以及
           后续n行是国家间的邻接矩阵表示
输出:遍历各国的最短路径长度。

输入举例:
4
0,1,2,3
1,0,4,5
2,4,0,2
3,5,2,0
本人算法方面是菜鸟,求各位大神帮忙解答。

2个回答

u011514451
u011514451   2016.09.18 09:54
u011514451
u011514451 http://blog.csdn.net/u011514451/article/details/39057103?locationNum=8
大约一年之前 回复
u011514451
u011514451 http://blog.csdn.net/u011514451/article/details/38494713?locationNum=4
大约一年之前 回复
u011514451
u011514451 回复datou123789: 没仔细读题,这应该是最小生成树问题,用普利姆算法可解决,以前写过,一时半会找不到了
大约一年之前 回复
datou123789
datou123789 好像要求不一样 我的是要求遍历
大约一年之前 回复
datou123789
datou123789 请问把邻接表中的值初始化为M(0x7f7f7f7f)是何用意呢?
大约一年之前 回复
Marksinoberg
Marksinoberg   Ds   Rxr 2016.09.18 10:33

博主之前也写过一个这方面的代码,拿过来改改估计就可以使用了。

 /**
 * @Date 2016年9月17日
 *
 * @author 郭  璞
 *
 */
package dynamic;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author 郭 璞 <br>
 *         求矩阵中从左上角到右下角的最短的距离
 *
 */
public class MinMatrixLength {

    public static void main(String[] args) {
        // int[][] matrix = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, {
        // 8, 8, 4, 0 } };
        int[][] matrix = { { 1, 0, 1, 1 }, { 0, 1, 0, 1 }, { 1, 1, 1, 0 }, { 0, 1, 0, 1 } };

        int minLength = getMinMatrixLength(matrix);
        System.out.println("最短的路径长度为:" + minLength);

        // 打印最短路径的详细节点
        Iterator<Integer> its = getMinMatrixLengthPath(matrix).iterator();
        while (its.hasNext()) {
            System.out.print(its.next() + "\t");
        }
        System.out.println();
    }

    public static int getMinMatrixLength(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return -1;

        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] dp = new int[rows][cols];
        dp[0][0] = matrix[0][0];

        // 求得第一列每层的路径长度
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }

        // 求得第一行的每层的路径长度
        for (int i = 1; i < cols; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }

        // 对于当前节点,最短路径为其左边一个或者上面一个中最小的那个加上当前位置的长度
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }

        // 返回矩阵中计算所得的最小路径和
        return dp[rows - 1][cols - 1];
    }

    /**
     * 求取最短路径上的节点时仍存在一些问题
     * 
     * @param matrix
     * @return
     */
    public static List<Integer> getMinMatrixLengthPath(int[][] matrix) {
        List<Integer> path = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return null;

        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] dp = new int[rows][cols];
        dp[0][0] = matrix[0][0];

        // 求得第一列每层的路径长度
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }

        // 求得第一行的每层的路径长度
        for (int i = 1; i < cols; i++) {
            dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }

        // 首先将(0,0)点添加到路径中
        path.add(matrix[0][0]);

        // 对于当前节点,最短路径为其左边一个或者上面一个中最小的那个加上当前位置的长度
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
                if (dp[i - 1][j] < dp[i][j - 1]) {
                    path.add(matrix[i - 1][j]);
                } else {
                    path.add(matrix[i][j - 1]);
                }
            }
        }

        // 将矩阵的右下角的终点添加到路径中
        path.add(matrix[rows - 1][cols - 1]);
        // 返回矩阵中计算所得的最小路径和
        return path;
    }
}

Marksinoberg
Marksinoberg 但是求path的那段代码仍然存在一点问题,只参考求最短路径长度的那个即可。
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片