精华内容
下载资源
问答
  • Java动态规划实现最短路径问题

    千次阅读 2019-07-20 21:08:00
    问题描述 给定一个加权连通图(无向的或有向的),要求找出从每个定点到其他所有定点之间的最短路径以及最短路径的长度。 2.1 ...

    问题描述

    给定一个加权连通图(无向的或有向的),要求找出从每个定点到其他所有定点之间的最短路径以及最短路径的长度。

    2.1 动态规划法原理简介
    动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

    与分治法最大的差别是:适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解)

    package com.liuzhen.floyd;
    
    public class Floyd {
    
        //根据有向图的权重矩阵及起始的中间节点路径矩阵,返回最终图的距离矩阵及中间节点路径矩阵
        public static void getShortestPath(int[][] chart,int[][] path){
            int len = chart.length;
            for(int k = 0;k < len;k++){  //k = 0表示,增加中间顶点a,k自增,表示后继增加第k个中间顶点(依次为b,c,d...)
              for(int i = 0;i < len;i++){        
                for(int j = 0;j < len;j++){
    
                    int temp = 0;   //新增一个中间顶点时,用该变量存储从i到k再到j的路径长度
                    if(chart[i][k] != 100 && chart[k][j] != 100)  //当A[i][k]和A[k][j]路径都可以行走,100表示两顶点不相通
                        temp = chart[i][k] + chart[k][j];
    
                    if(chart[i][j] > temp  && temp != 0) {    //如果当前i到j路径长度(包括无法达到情况)大于以k为中间顶点的路径时
                        chart[i][j] = temp;
                        path[i][j] = k+1;   //当两顶点相通,且是最短路径时,把k+1存入中间节点路径矩阵path中(PS:0表示i到j之间没有中间节点,1表示中间节点为a,所以此处为k+1,而不是用k,这样排除0的情况)
                    }
                }  
              }
            }
        }
        
        //根据有向图的中间节点路径矩阵,以及两个顶点,返回这两个顶点之间的最短路径
        public static String getOneShortestPath(int[][] path,int start,int end){
            char startNode = (char) ('a' + start);
            char endNode = (char) ('a' + end);
            String nodePath = "";
            if(path[start][end] == 0){
                nodePath += startNode+"->"+endNode;
                return nodePath;
            }
            int middle = path[start][end]-1;
            //使用递归求解最短路径
            nodePath += getOneShortestPath(path,start,middle)+" , "+getOneShortestPath(path,middle,end);
            return nodePath;
        }
        
        //输出有向图所有顶点之间的最短路径及最短路径长度
        public static void printShortestPath(int[][] path,int[][] result){
            int len = path.length;
            for(int i = 0;i < len;i++){    
                char startNode = (char) ('a' + i);
                for(int j = 0;j < len;j++){
                    char endNode = (char) ('a' + j);
                    String ijPath = startNode+"——>"+endNode+"最短路径为:";
                    String nodePath = getOneShortestPath(path,i,j);    
                    System.out.println(ijPath+nodePath+" 。 路径长度为:"+result[i][j]);
                    }        
            }
        }
        
        public static void main(String args[]){
            /*chart数组中,数组0,1,2,3等表示两顶点之间的权重值,即两顶点间的距离大小, 100表示两顶点不相通*/     
            int[][] chart = {{0,100,3,100},{2,0,100,100},{100,7,0,1},{6,100,100,0}};
    
            System.out.println("有向图chart的权重矩阵为(PS:其中值为100表示无穷大,即无法相通的路径):");
            System.out.println("\t"+"a"+"\t"+"b"+"\t"+"c"+"\t"+"d");
            for(int i = 0;i < 4;i++){
                char startNode = (char) ('a' + i);
                System.out.print(startNode+"\t");
                for(int j = 0;j < 4;j++)
                    System.out.print(chart[i][j]+"\t");
                System.out.println();    
            }
            /*path数组中,0表示两顶点相通,1表示两顶点间有一个中间节点a,2表示 两顶点间有一个中间节点b,3两顶点间有一个中间节点c,4两顶点间有一个中间节点d.
             * 100表示两顶点不相通*/
            int[][] path = {{0,100,0,100},{0,0,100,100},{100,0,0,0},{0,100,100,0}};
            getShortestPath(chart,path);    
    
            System.out.println("有向图chart的距离矩阵为:");
            System.out.println("\t"+"a"+"\t"+"b"+"\t"+"c"+"\t"+"d");
            for(int i = 0;i < 4;i++){
                char startNode = (char) ('a' + i);
                System.out.print(startNode+"\t");
                for(int j = 0;j < 4;j++)
                    System.out.print(chart[i][j]+"\t");
                System.out.println();    
            }
    
            System.out.println("有向图chart的中间节点路径矩阵为(PS:值为0表示两节点直接相通,值为1表示两节点有一个中间节点a,值为2表示中间节点为b,依次类推):");
            System.out.println("\t"+"a"+"\t"+"b"+"\t"+"c"+"\t"+"d");
            for(int i = 0;i < 4;i++){
                char startNode = (char) ('a' + i);
                System.out.print(startNode+"\t");
                for(int j = 0;j < 4;j++)
                    System.out.print(path[i][j]+"\t");
                System.out.println();    
            }
    
            System.out.println("最终求取结果为:");
            printShortestPath(path,chart);
            
            
        }
    }
    
    有向图chart的权重矩阵为(PS:其中值为100表示无穷大,即无法相通的路径):
        a    b    c    d
    a    0    100    3    100    
    b    2    0    100    100    
    c    100    7    0    1    
    d    6    100    100    0    
    有向图chart的距离矩阵为:
        a    b    c    d
    a    0    10    3    4    
    b    2    0    5    6    
    c    7    7    0    1    
    d    6    16    9    0    
    有向图chart的中间节点路径矩阵为(PS:值为0表示两节点直接相通,值为1表示两节点有一个中间节点a,值为2表示中间节点为b,依次类推):
        a    b    c    d
    a    0    3    0    3    
    b    0    0    1    3    
    c    4    0    0    0    
    d    0    3    1    0    
    最终求取结果为:
    a——>a最短路径为:a->a 。 路径长度为:0
    a——>b最短路径为:a->c , c->b 。 路径长度为:10
    a——>c最短路径为:a->c 。 路径长度为:3
    a——>d最短路径为:a->c , c->d 。 路径长度为:4
    b——>a最短路径为:b->a 。 路径长度为:2
    b——>b最短路径为:b->b 。 路径长度为:0
    b——>c最短路径为:b->a , a->c 。 路径长度为:5
    b——>d最短路径为:b->a , a->c , c->d 。 路径长度为:6
    c——>a最短路径为:c->d , d->a 。 路径长度为:7
    c——>b最短路径为:c->b 。 路径长度为:7
    c——>c最短路径为:c->c 。 路径长度为:0
    c——>d最短路径为:c->d 。 路径长度为:1
    d——>a最短路径为:d->a 。 路径长度为:6
    d——>b最短路径为:d->a , a->c , c->b 。 路径长度为:16
    d——>c最短路径为:d->a , a->c 。 路径长度为:9
    d——>d最短路径为:d->d 。 路径长度为:0
    
    展开全文
  • 主要介绍了Java实现利用广度优先遍历(BFS)计算最短路径的方法,实例分析了广度优先遍历算法的原理与使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • floyd 弗洛伊德最短路径 java实现,需要自己定义邻接矩阵
  • 动态规划思想解决最短路径问题java语言实现
  • 动态规划之求最短路径java版)

    万次阅读 2017-04-13 19:32:46
    最短路径众所周知有Dijistra算法、Bellman-ford等,除了这些算法,用动态规划也可以求出最短路径,时间复杂度为O(n^2),跟没有优化的Dijistra算法一样(优化后的Dijistra算法时间复杂度为O((m+n)lgn))。...

    求最短路径众所周知有Dijistra算法、Bellman-ford等,除了这些算法,用动态规划也可以求出最短路径,时间复杂度为O(n^2),跟没有优化的Dijistra算法一样(优化后的Dijistra算法时间复杂度为O((m+n)lgn))。
    这里写图片描述
    首先这里有15个结点,表现出来的矩阵为
    这里写图片描述
    左侧1-15表示前一个节点,最上面一行1-15表示后一个节点,记这个图的矩阵为P,那么P[0][1]==5表示节点0与节点1相连,路径长度为5。那么我们如何利用动态规划来求解最短路径?

    首先我们需要把整个问题转换成小的子问题,利用小的子问题的最优解求出整个问题的最优解。

    我们的目的是求0-15之间的最短路径,由图可知与节点15相连的是结点14和节点13,假设我们已经求出0-13的最短路径的值D13和0-14的最短路径的值D14,那么我们只需要比较D13+d(13-15)和D14+d(14-15)的大小就可以知道从哪个节点出发到节点15的路径最短。按照这个思想一直往前推,推到节点0时结束,自然就求出了节点0-节点15的最短路径,这个思路是递归的,如果用递归的方法,时间复杂度很高,当然你也可以用备忘录,记录已经计算过的值,我这里将递归转换成迭代。

    我们先定义一个类class Node,里面存储节点的序号、从0到这个节点的最短路径的值、前一个节点的序号。

    class node{
        public int number;
        //value是指从0到这个节点总共要走多远,执行算法前将value的值初始化为无穷大
        public int value;
        public int parent;
    }

    图的矩阵自己存一下,我这里不写了

    //从矩阵a的第一行开始,一行行找相连的节点
    for(int i = 0;i<16;i++){
                for(int j = 0;j<16;j++){
                //找到了相连节点
                    if(a[i][j]!=0){
                    //上一个节点的最短路径的值+与下一个节点相连路径上的值
                        d = n[i].value+a[i][j];
                        //判断是否比原先的值要小,如果小就将0-j节点的长度替换
                        if(d<n[j].value){
                            n[j].value = d;
                            //记录前一个节点的序号
                            n[j].parent = i;
                        }
                    }
                }
            }

    最后将n[15].value打印出来就是最短路径的值,再根据parent的值往前找就得到最短路径的解,当然这个例子有不同的路径的解,虽然值一样,我这里只给了一种。

    这里写图片描述

    展开全文
  • 主要为大家详细介绍了Java实现Floyd算法求最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 重点掌握:动态规划法求解每对结点之间的最短路径、0/1背包问题。 如果求任意两点之间的最短路径,两点之间可以直接到达但却不是最短的路径,要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点...
  • Floyd最短路径java实现

    2017-12-15 16:28:54
    Floyd最短路径算法的java实现,文件内附测试用例拓扑。
  • 主要为大家详细介绍了java使用Dijkstra算法实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • JAVA动态规划解决最短路径问题 啊
  • 动态规划——最短路径

    千次阅读 2019-10-19 15:43:06
    ,棋子从左上角出发,到右下角,求经过的最短路径。矩阵中每个数值代表距离的长度。 分析:从[0][0]到[n-1][n-1],每个阶段都有两种决策,向下或向右。 1. 贪心算法 一条路走到黑,只选择下一步中较小值。 #...

    题目:

    有一个n*n的矩阵WW[n][n],存储正整数   int WW[4][4] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3}; ,棋子从左上角出发,到右下角,求经过的最短路径。矩阵中每个数值代表距离的长度。

     分析:从[0][0]到[n-1][n-1],每个阶段都有两种决策,向下或向右。

    1. 贪心算法

    一条路走到黑,只选择下一步中较小值。

    #define N 4
    int minDistGreedy(int w[N][N])
    {
    	int result = w[0][0];
    	int i = 0, j = 0;
    	while(i < N && j < N)
    	{
    		if(w[i+1][j] < w[i][j+1])	    // 向下
    		{
    			result += w[i+1][j];
    			++i;
    			if (i == N-1 && j < N-1)	// 向下走完,但右边没走完
    			{
    				while(j < N-1)
    				{
    					result += w[i][j+1];
    					++j;
    				}
    				break;
    			}
    		}
    		else
    		{
    			result += w[i][j+1];	    // 向右
    			++j;
    			if (j == N-1 && i < N-1)	// 向右走完,但下边没走完
    			{
    				while(i < N-1)
    				{
    					result += w[i+1][j];
    					++i;
    				}
    				break;
    			}
    		}
    	}
    	return result;
    }
    int main()
    {
        int WW[4][4] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};
        cout << "贪心算法求的最短距离:" << minDistGreedy(WW) << endl;    // 19
        system("pause");
        return 0;
    }

    2. 回溯算法

    总共要走2*(n-1)步

    #define N 4
    int minDist = 65535;
    void minDistBT(int i, int j, int dist, int w[4][4], int n)
    {
    	if (i == n-1 && j == n-1)
    	{
    		if (dist+w[i][j] < minDist)    // 此处对最后一个数,进行了特殊处理。因为递归没有处理到
    		{
    			minDist = dist+w[i][j];
    		}
    		return;
    	}
    	if (i < n)
    	{
    		minDistBT(i+1, j, dist+w[i][j], w, n);
    	}
    	if(j < n)
    	{
    		minDistBT(i, j+1, dist+w[i][j], w, n);
    	}
    }
    
    int main()
    {
    	int WW[4][4] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3}; 
    	minDistBT(0,0,0,WW,4);
    	cout << minDist << endl;    // 输出19
    	system("pause");
    	return 0;
    }

    关于重复计算的步数,可以通过添加【备忘录】的方式,省去递归。即已经算过的,就不用再计算了。

     3. 动态规划

    f(i,j,dist);  // i,j 表示位置,dist 表示当前所走的路径长度。 

     

    找到公式:min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))   最短路径等于当前值加上左边上边的较小值。

    有了回溯代码之后,画出递归树,找到重复子问题,即重复走过的位置(i,j)相等,但距离不等,取最小。

       

    #define N 4
    int minDistDP(int w[4][4])
    {
    	int states[N][N] = {0};
    	int sum = 0;
    	for (int j = 0; j < N; ++j)		// 初始化states的第一行数据
    	{
    		sum += w[0][j];
    		states[0][j]=sum;
    	}
    	sum = 0;
    	for (int i = 0; i < N; ++i)		// 初始化states的第一列数据
    	{
    		sum += w[i][0];
    		states[i][0] = sum;
    	}
    	for (int i = 1; i < N; ++i)
    	{
    		for (int j = 1; j < N; ++j)
    		{
    			states[i][j] = w[i][j]+min(states[i-1][j], states[i][j-1]);
    		}
    	}
    	return states[N-1][N-1];
    }
    int main()
    {
        int WW[4][4] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};
        cout << "最短距离为:" << minDistDP(WW) << endl;    // 19
        system("pause");
        return 0;
    }

     

    展开全文
  • 对应的算法书这块,大家可以在学习算法时就会接触到关于最短路径的求解。 例图: 就是在这样的图去寻找V1到V5的最短路径。 那么思路是什么? 明确目标: V1到V5 并且是一个可通图 路径长度最短 这样一来思路就很...

    多端图的描述其实就是有向图。对应的算法书这块,大家可以在学习算法时就会接触到关于最短路径的求解。
    例图:
    在这里插入图片描述
    就是在这样的图去寻找V1到V5的最短路径。
    那么思路是什么?
    明确目标:

    • V1到V5
    • 并且是一个可通图
    • 路径长度最短
      这样一来思路就很清晰。设立数组value[]来表示对应到12个端点的最值。value[i]表示由0-i 的最短路径。
      对应的代码:
      public static int []value;
    	public static int fun(int[][] arr, int a) {
    		value = new int[arr.length];
    		Arrays.fill(value, Integer.MAX_VALUE);
    		int[] parent = new int[arr.length];
    		Arrays.fill(parent, -1);
    		value[0]=0;
    		parent[0]=-1;
    		for (int j = 1; j < arr.length; j++) {
    			for (int i = j - 1; i >= 0; i--) {
    				if (arr[i][j] != a) {
    					int d = value[i] + arr[i][j];
    					if (d < value[j]) {
    						value[j] = d;
    						parent[j] = i;
    					}
    				}
    			}
    		}
    		return value[arr.length - 1];
    	}
    

    用例:

    public static void main(String[] args) {
    		int a = Integer.MAX_VALUE;
    		int[][] arr = new int[][] { { a, 2, 3, 1, a }, { a, a, a, a, 5 }, { a, a, a, a, 3 }, { a, a, a, a, 7 },
    				{ a, a, a, a, a } };
    		System.out.println(fun(arr, a));
    		for(int i=0;i<value.length;i++) {
    			System.out.print(value[i]+" ");
    		}
    
    	}
    

    用例图解:
    在这里插入图片描述

    展开全文
  • java数据结构课程设计校园超市选址中,我们要用到弗洛伊德算法输出最短路径最短路径长度,输出的路径用点--->点表示,本文件提供输出的代码。
  • 给定先把图 G(V,E),用动态规划的算法求一条从起点到终点的路径,使这条路径上经过的所 有边的权重之和最小。 2. 算法描述 2.1 动态规划描述 动态规划是一种用来解决一类最优化问题的算法思想,将一个复杂的问题...
  • 书本上的算法只是给出了最短距离的求法,没有给出最短路径的实现。代码在迪杰斯特拉的基础上加以改进,能求图中任意两点的最短距离和所有的最短路径(如果存在多条最短路径)。将结果存储在一个HashMap中。
  • NULL 博文链接:https://128kj.iteye.com/blog/1678532
  • Java)求两顶点间最短路径和距离 在网上查看了一些博客,发现他们的代码都有些问题,于是自己重新写了一个,有一定注释
  • java单源最短路径(贪心算法) public class TheShortestWay { static int MAX_SIZE = 6; public static void dijkstra(int v, float[][] a, float[] dist, int[] prev) { int n = dist.length - 1; if (v ||...
  • java 最短路径 问题 动态规划java 最短路径 问题 动态规划
  • 路径上所有的数字累加起来就是路径的和,返回所有的路径中的最小的路径的和。 如果给定的m如大家看到的样子,路径1,3,1,0,6,1,0是所有路径路径和最小的,所以返回12. 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 思路: 式...
  • java实现单源最短路径

    2020-08-26 10:27:16
    主要为大家详细介绍了java实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • NULL 博文链接:https://dongbiying.iteye.com/blog/1162366
  • 主要介绍了java实现最短路径算法之Dijkstra算法, Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法,有兴趣的可以了解一下
  • 7*5矩阵方格中,红色A绕过障碍物到达B,移动规则: 1.A向周围8个小方格移动但是不能移动到旁边有球的方格 2.A球需要用最短路径到达B 求:用java实现该算法
  • 数据结构中最短路径的实现,用的是java语言,很简单很实用
  • 算法设计与分析课内实验——动态规划求单源最短路径。文档很齐全,包括算法分析过程和源代码(java语言eclipse环境)
  • 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个整数。另外,还给定 V 中的一个顶点,...现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
  • dijkstra 迪杰斯特拉 最短路径 java实现
  • 主要为大家详细介绍了java实现Dijkstra最短路径算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,744
精华内容 15,497
关键字:

动态规划最短路径java

java 订阅