2 dgghjnjk dgghjnjk 于 2016.03.06 10:55 提问

有一个算法问题,与图论有关

给定一个有向无环权重图G(V,E),V的一个子集为V',从给定的点s出发到给定的点t,找出一条能遍历V'的最短路径,已知权重为1到20的整数。

4个回答

dgghjnjk
dgghjnjk   2016.03.06 10:56

求思路啊!图片说明图片说明图片说明图片说明图片说明

u013596119
u013596119   Rxr 2016.03.06 11:06

昨天刚和问答的一个朋友讨论过

 有一带权重的有向图,给定起点B,终点E,以及n个必须经过的点,通过编程算出权重最小的点。

他的问题是np。。。。
但是你的貌似不是,因为你的G确定不包含环,![图片说明](https://img-ask.csdn.net/upload/201603/06/1457233379_894907.jpg)图片说明

这是我写的算法,用dfs遍历所有s到t的路径,选出路过v‘的比较,

还有一个算法,用floyd计算v'中所有点两两的最短距离,然后全排列,然后在看s,t,这个算法在v’数量较小的情况可以实现,但是v‘数量太大就要越界了

u013596119
u013596119   Rxr 2016.03.06 11:06

还有一张图。。。图片说明

Techay
Techay   2016.03.06 11:39

这不是华为的题吗,这样不好吧

dgghjnjk
dgghjnjk 只是想和大家讨论一下,获得更多的思路,并不是来找答案的
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
图论中的常见算法分析比较和模板
图论小结(一)     从一开始搞ACM到现在也有几个年头了,而搞图论的时间可是从一开始搞ACM开始。所以,总是对图论有着一种独有的感情。图论的内容说难不难,但是确实在算法中日常生活中可以经常遇到,且一个很有趣的算法。这也是我当初选择图论的原因,但是图论的代码量一般都比较的大,当初就是看到别人啪啪的一下只就敲出了几百行的图论代码,而自己当时是佩服的不得了啊。可是进入图论后,才发现,一照进
图论的各种基本算法
本篇主要涉及到图论的基本算法,不包含有关最大流的内容。图论的大部分算法都是由性质或推论得出来的,想朴素想出来确实不容易。二分图(Is-Bipartite)一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度顶点分别在这两个子集中。这个问题可以转换为上篇提到过的图的着色问题,只要看图是否能着2个颜色就行了。当然,可以回溯解决这个问题,不过对于着2个颜色可以BFS解决。同样,一维数组colors
图论算法进阶习题集-500题

趣味数学---图论四人过桥
有一天晚上,有四个人需要通过架在山谷间的危桥,任意时刻最多只能有两个人在桥上,过桥需要一盏闪光灯,这些人只有一盏闪光灯。如果单独过桥他们分别需要10、5、2、1分钟,如果两人同时过桥则所需时间是较慢者所需的时间。18分钟后,沿山谷滚滚而下的山洪将把这座桥冲毁。这四个人能及时过桥吗?不用图论知识,证明你的结论;并说明如何用图论知识获得答案。 分析:一共有四个人,一个手电筒,如果群聚的话
基本图论算法--《算法导论》
广度优先搜索(BFS)算法描述对于一个给定的图G(V,E)G (V,E) 和一个源节点SS BFS能遍历所有从SS出发能到达的节点,并计算SS 能到达每一个节点的距离(最少的边数),并生成一可广度优先搜索树。代码说明u.pu.p uu的前驱结点 u.du.d uu到SS的距离 u.coloru.color uu的状态,WHITE 未被搜索到,GRAY正在被发现,BLACK以搜索结束 QQ 队列
数学建模中的图论问题
作用选址问题、指派问题、运输问题、旅行商问题和中国邮递员问题等各相关算法(C++实现)单源最短路径-Dijkstra 最小生成树-Kruskal 二分图匹配 网络最大流-Edmonds Krap 网络最大流-Dinic Floyd多源最短路径 二分图的覆盖与独立集
图论算法总结
网络流 Dinic算法 约瑟夫问题 匈牙利算法 最小费用最大流 字符串 最长回文串 KMP算法 最长递增子串 最大公共子串 树状数组 线段树 字典树 莫队算法 树形dp 背包问题 最短路 Dijkstra算法和Floyd算法 spfa算法 Bellman-Ford算法 最小生成树 并查集
图论算法---- 一笔画问题(欧拉路)
一、题目描述 题目描述 对给定的一个无向图,判断能否一笔画出。若能,输出一笔画的先后顺序,否则输出“No Solution!” 所谓一笔画出,即每条边仅走一次,每个顶点可以多次经过。 输出字典序最小的一笔画顺序。 输入 第1行:1个整数n,表示图的顶点数(n 接下来n行,每行n个数,表示图的邻接矩阵 输出 第1行:一笔画的先后顺序,每个顶点之间用一个空格分开 样例输
简单的图论问题(Dijkstra)
O - 简单的图论问题? Time Limit:5000MS     Memory Limit:65535KB     64bit IO Format: Submit Status Description 给一个 n 行 m 列的迷宫,每个格子要么是障碍物要么是空地。每个空地里都有一个权值。你的 任务是从找一条(r1,c1)到(r2,c2
一笔画问题【数据结构-图论】
回家路上听到2个人在说:田字怎么一笔写成,并且笔划不重复。田我回家想了许久,觉得无论如何走正常的途径肯定是不行的,投机取巧脑筋急转弯的我不讨论。那么是否可以找到数学定理?其实就是欧拉七桥问题:18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?欧拉于1736年研究并解决了此