精华内容
下载资源
问答
  • 内包含QT程序,运行出来是一个60*60的迷宫,算法包括迷宫的自动生成,利用深度优先搜索、广度优先搜索两种方法遍历最短路径,并能在界面上动态显示。
  • 本题要求是求遍历所有节点的最短路径,由于本题中是没有要求一个节点只能访问一次的,也就是说可以访问一个节点多次,但是如果表征两次节点状态呢?可以使用(curNode, VisitedNode)来进行表征,如果两次的已经...

    2018-10-06 22:04:38

    问题描述:

    问题求解:

    本题要求是求遍历所有节点的最短路径,由于本题中是没有要求一个节点只能访问一次的,也就是说可以访问一个节点多次,但是如果表征两次节点状态呢?可以使用(curNode, VisitedNode)来进行表征,如果两次的已经访问的节点相同那么就没有必要再进行访问了,最终的状态就是所有节点都访问过了。

    另外,由于起点对结果是有影响的,因此在最开始需要将所有的节点都压栈。

        public int shortestPathLength(int[][] graph) {
            int n = graph.length;
            int[][] used = new int[n][1 << n];
            Queue<int[]> q = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                used[i][1 << i] = 1;
                q.add(new int[]{i, 1 << i});
            }
            int step = 0;
            while(!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    int[] curNode = q.poll();
                    int node = curNode[0];
                    int state = curNode[1];
                    if (state == ((1 << n) - 1)) return step;
                    for (int k : graph[curNode[0]]) {
                        int newState = state | (1 << k);
                        if (used[k][newState] == 1) continue;
                        used[k][newState] = 1;
                        q.add(new int[]{k, newState});
                    }
                }
                step++;
            }
            return -1;
        } 
    

     

    转载于:https://www.cnblogs.com/hyserendipity/p/9748760.html

    展开全文
  • 此题有点难,参考了这篇文章,是个两条路的DP: http://blog.csdn.net/a83610312/article/details/12522077一句话:这个跟从起点直接引两条路径出去是一样的,一条到达 i 点,一条到达 j 点 .然后用DP做。 首先要...

    http://www.itint5.com/oj/#50

    此题有点难,参考了这篇文章,是个两条路的DP: http://blog.csdn.net/a83610312/article/details/12522077
    一句话:这个跟从起点直接引两条路径出去是一样的,一条到达 i 点,一条到达 j 点 .然后用DP做。

    首先要认识到,从起点引出两条路,上面到i点,下面到j点,和上面到j点,下面到i点,是对称的。如图所示(红色代表从左向右走,蓝色代表从右向左走,蓝色和红色可能有交叉,这里为了简单,未画出):

         

    这里用cost[i][j]表示按照上述表示的两条路径的最短距离。由于对称性,只需要考虑i>j的情况。关于转移方程,有两种情况:
    如果i>j+1,也就是i和j不挨着,那么比较简单,i肯定是从i-1过来的(由于两条路径的假设),所以cost[i]=cost[i-1][j]+dist[i-1][i] (dist表示两个点的距离)如果所示:

    如果i==j+1,也就是i和j挨着,那么也就是说上线中除i之外的所有点都在j的左边,那么以i和j结尾的情况里,上线中i可能从任何一个之前的点k过来,所以要遍历,看cost哪种情况最小。如下所示(右图表示k可能的一种情况):

         

     

    转载于:https://www.cnblogs.com/lautsie/p/3778417.html

    展开全文
  • 最短路径遍历树-----(旅行商问题)

    千次阅读 2011-05-06 09:15:00
    前天,同学参加数学建模比赛,他们选的题目是垃圾分类处理与清运方案设计,其中他们要我帮他们写出一...这样子,你从任一站点出发,应该会有唯一的最短路线。 我花了半天时间去研究,发现除了遍历所有路线之外别无他法

        前天,同学参加数学建模比赛,他们选的题目是垃圾分类处理与清运方案设计,其中他们要我帮他们写出一个能用最少花费遍历所有垃圾站点的一条路线。扎看一下,还以为是求出最段路径,直接用Dijkstra算法就可以处理了。但是仔细一想不对劲,这题目不是那么简单求出顶点之间的最优路径,还要类似一笔画一样,求出一条能一笔连到底的路线,当然若这样则现实要求比较苛刻,各个垃圾站点必须能够相通,即该图是强连通图。这样子,你从任一站点出发,应该会有唯一的最短路线。

        我花了半天时间去研究,发现除了遍历所有路线之外别无他法。后来上网一查,原来这有点类似旅行商问题,但又不完全是。旅行商问题更难一点,它不要求图是强连通图,看似这类题目简单,其实但端点数目多了,求解极为复杂。当端点达到一定数目时候,如果要列举所有路径后再确定最佳行程,那么总路径数量之大,几乎难以计算出来。 但我这类问题,好像有人取得了突破,采用了“蚁群算法”,是Marco Dorigo于1992年在他的博士论文中提出。蚁群算法其实挺简单的,就是遍历所有路线,然后找出最优路线,最终就是采用那个方案了,这也是蚂蚁觅食的方式。基于这种思想,我写出了一下的代码,代码不难,难就难在如何遍历所有路线及判断最短路线,如果单单保存所有路线,这就对存储空间要求比较高了,但端点数目每增加一个,原先一条完整路线又会在原来路线上多出n-2条。这对内存挑战极大哦!! 所以我采用了回溯法思想。 以下是我个人代码。。。

       

    展开全文
  • 可以用邻接表和邻接矩阵求最短路径 实现图的邻接矩阵和邻接表存储结构; 完成基于邻接矩阵或邻接表的深度优先搜索遍历及广度优先搜索遍历; 实现从键盘输入任意一对顶点,求出顶点间的最短路径
  • } int f(int n, int len) {//len:初值定为2,用来操作遍历过的数组 b[0] = 0; b[1] = 1; //int k; //int num;//有几组 if (n == 9) { //printf("%d:", num); int energy = 0; for (int i = 1; i ; i++)...

    C:

    #include<stdio.h>
    #define SIZE 100
    
    int map[SIZE][SIZE];
    int len[SIZE];
    
    int b[SIZE];
    int e = 12; //边
    int v = 9; //点
    
    
    
    void main() {
    
    	for (int i = 1; i <= v; ++i) {	//设一开始每个点都不可达 
    		for (int j = 1; j <= v; ++j) {
    			map[i][j] = 0;
    		}
    	}
    
    	//输入边的能量
    	map[1][2] = 3;
    	map[1][4] = 1;
    	map[2][3] = 4;
    	map[2][5] = 6;
    	map[3][6] = 10;
    	map[4][5] = 2;
    	map[4][7] = 5;
    	map[5][6] = 5;
    	map[5][8] = 6;
    	map[6][9] = 6;
    	map[7][8] = 3;
    	map[8][9] = 7;
    
    	for (int i = 1; i <= v; i++) { //使之成为无向图
    		for (int j = 1; j <= v; j++) {
    			if (map[i][j] != 0)
    				map[j][i] = map[i][j];
    		//	printf("%d", map[i][j]);
    		}
    	//	printf("\n");
    	}
    
    
    	f(1, 2);
    }
    
    int f(int n, int len) {//len:初值定为2,用来操作遍历过的数组
    	b[0] = 0;
    	b[1] = 1;
    	//int k;
    	//int num;//有几组
    	if (n == 9) {
    		//printf("%d:", num);
    		int energy = 0;
    		for (int i = 1; i < len; i++) {
    			printf("%d ", b[i]);
    			if (i < len - 1) {
    				energy += map[b[i]][b[i + 1]];
    			}
    
    
    
    
    		}
    		//printf("\n");
    		printf("energy=%d\n", energy);//每条线的能量
    
    	}
    	else {
    		for (int i = 2; i <= v; i++) {
    			int k = 1;
    				while (k < len && map[n][i] != 0) { 
    				//判断之前是否遍历过这个点
    					if (b[k] == i)
    						break;
    					else
    						k++;
    				}
    			if (k == len ) {
    			 //没遍历过,即没有跳出循环,k=len
    				b[len++] = i;
    				f(i, len);
    				len--;
    			}
    
    		}
    	}
    	return;
    }
    
    
    

    shell:

    (后续补充)

    展开全文
  • 蚁群算法解决城市遍历最短路径...这个是完整的城市最短路径遍历问题,函数是从网上下载的,不过我自己做了testant.m程序,完全可以调试通过,对初学者有一定得帮助。  只需要运行testant.m程序即可,可以输出试验结果
  • 图 等价类 数据结构 堆 BFS DFS Prim KrustalDijkstra Floyd 的实现
  • 我们遍历最短时间。 for(int i=0;i;i++){ for(int j=0;j;j++){ if(graph[i][j]=='@'){ result=min(result,dis[0][i][j]+dis[1][i][j]); } } } cout*result; } return 0; }
  • ![图片说明](https://img-ask.csdn.net/upload/201811/11/1541874535_433755.png 谁能快点解决?、 ????
  • 广度遍历最短路径

    2018-12-01 00:49:59
    存储结构:邻接表; 实现功能:广度遍历最短路径; 博客中的代码实现
  • 图的广度优先遍历最短路径算法

    万次阅读 多人点赞 2018-09-12 19:33:42
    图的广度优先遍历最短路径算法 前言 广度优先遍历算法的探讨 核心代码分析 测试用例 完整代码获取 博客文章版权声明 图的广度优先遍历最短路径算法 前言 上一次,我们讨论了有关图的深度优先遍历算法...
  • 由于产品的需求,现要对一批又起始站的站点规划一条最短路径出来。需求大概就是下图的意思: 再查询了最短路径算法后,Dijkstra算法和Floyd算法后,感觉不符合我的需求,然后就自己琢磨写一个算法出来。 ...
  • 线段遍历最短路径

    2013-05-16 09:38:09
    在平面内,自动生成N条线段,用遍历线段中点开始,采用镜像原理,求出最短距离点,求最短到达路径
  • //x , y 即用户想要查找从x到y的最短路径 void BFSTraverse(Graph G , char x , char y){ Queue Q; Init(Q); int i; for(i = 1 ; i ; i++){ visited[i] = 0; } //用于存放用户指定的开始点下标 int start; //获得...
  • 简单图论:遍历所有最短路径

    千次阅读 2019-11-22 10:51:04
    今天遇到了两道要求遍历所有最短路径的题,我一直做不对的原因竟是我把无向图当成了有向图,郁闷的要死。 解决遍历所有最短路径,其实思路很简单,首先通过经典算法[各种算法,求出最短路径的长度,然后就只能DFS来...
  • 遍历最短路径

    2019-07-30 21:39:22
    // ConsoleApplication21.cpp: 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <stdio.h>   #include <iostream>   #include <math.h> int orderRoute[120][5];...u...
  • 最短路径 –在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的路劲。 单源最短路径 –从某固定源点出发的最短路径 无权图的最短路径 按照路径长度递增的顺序找出源点到各个顶点的最短路径 类似于...
  • 广度优先遍历求出了无权图的最短路径; 用广度优先遍历求无权图的最短路径代码实现 广度优先遍历的过程中会记录每个节点到标定点的距离到数组 ord 中; 某个点到标定点的最短路劲就存储在数组 ord 中; package...
  • C# 图的遍历最短路径

    2008-07-09 13:42:14
    C# 图的遍历最短路径
  • Dijkstra算法适用于求一个节点到其他节点的最短路径,主要特点是通过广度搜索(由近及远、层层扩展)来遍历其他所有需要求距离的点的思想来解决最短路径问题。 一个辅助数组D,记录从起始节点到当前节点的最短距离...
  • C++ DijkStra最短路径(输出两点间最短路径与线路)

    万次阅读 多人点赞 2018-07-03 21:22:51
    因为Dijkstra迪杰斯特拉算法每次都是从...(1)图算法之最短路径(Dijkstra) (2)DijkStra最短路径的C++实现与输出路径  (3) 柳诺-【最短路径】之Dijkstra算法 (4) DijkStra最短路径的C++实现与输出路径 ...
  • 文章目录一、图的定义1、图的介绍2、加权图二、图的存储1、邻接矩阵:2、邻接表三、图的遍历1、深度优先遍历(DFS)2、广度优先遍历(BFS)3、最短路径1、最短路径(1)2、最短路径(2) 一、图的定义 1、图的介绍 图...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,540
精华内容 1,416
关键字:

最短路径遍历