logo
Redian新闻
>未名空间
>Programming - 葵花宝典
>
这个图问题的复杂度是多少呢
avatar
这个图问题的复杂度是多少呢# Programming - 葵花宝典
k*f
1 楼
一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
要求从第一个节点到第n个节点找出k条不同路径
这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
要求k条路径的权重总和最小。
当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
当k＝2以上的时候，好像就不好解了。
avatar
e*w
2 楼
一共就n个节点，怎么才能让k条路“经过的节点都不相同”？

同。

【在 k****f 的大作中提到】
: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。
avatar
k*f
3 楼
有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node

【在 e*****w 的大作中提到】
: 一共就n个节点，怎么才能让k条路“经过的节点都不相同”？
:
: 同。
avatar
e*w
4 楼
i see. 贪心好像不行，貌似有点小难。

【在 k****f 的大作中提到】
: 有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node
avatar
s*u
5 楼
网络流

同。

【在 k****f 的大作中提到】
: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。
avatar
k*f
6 楼
关键是有两个路径之间不能有公共的点(除了首尾)，
这个约束处理起来比较麻烦的。

【在 s****u 的大作中提到】
: 网络流
:
: 同。
avatar
s*u
7 楼
一个点拆两个点，容量1，费用0
很常规的处理方法吧

【在 k****f 的大作中提到】
: 关键是有两个路径之间不能有公共的点(除了首尾)，
: 这个约束处理起来比较麻烦的。
avatar
k*f
8 楼
能不能具体说说么？
有k个flow的

【在 s****u 的大作中提到】
: 一个点拆两个点，容量1，费用0
: 很常规的处理方法吧
avatar
s*u
9 楼
每个点V拆成两个点X,Y
除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
最后求一个从源到汇的最小费用最大流

【在 k****f 的大作中提到】
: 能不能具体说说么？
: 有k个flow的
avatar
k*f
10 楼
多谢了！！

【在 s****u 的大作中提到】
: 每个点V拆成两个点X,Y
: 除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
: 如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
: 对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
: 最后求一个从源到汇的最小费用最大流
avatar
s*u
11 楼
对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-

【在 k****f 的大作中提到】
: 多谢了！！
avatar
k*f
12 楼
呵呵，还在复习network flow算法，
我的问题C刚好是1。

【在 s****u 的大作中提到】
: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
avatar
k*f
13 楼
顺便再问问
如果题目改成：
k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
能不能用同样的技巧呢？

【在 s****u 的大作中提到】
: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-
avatar
s*u
14 楼
同样做法不行吧 -_-
去想想..

【在 k****f 的大作中提到】
: 顺便再问问
: 如果题目改成：
: k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
: 能不能用同样的技巧呢？
相关阅读
J2EE 的面试 越来越变态 (转载)有懂bigtable ,hbase，c*的么？问一个timestamp的问题何用openpyxl 从excel 文档的某一行读起？Vert.x在招人现在最流行的分布式kv store是什么感觉google的infra最近老是出问题雅虎裁员背后：动荡的IT行业 员工要提高自身反脆弱性clojure这符号花花绿绿的 也是醉了app单干没啥前途吧？Python 这种二逼语言怎么设计的谁能给我一个TestFlight invitation code ? (转载)C 语言，2进制转16进制，输入问题Scala Exercises The easy way to learn Scala.才知道liteIDE是国人的牛作！更要支持我想在iPad上实现Restful与服务器通信，大家一般都是怎么做的？Need a Jr developer (转载)正则表达式里括号的转义好乱游戏的后端用什么工具？为什么天朝没有发明任何有用的计算机语言？ (转载)大家来算算数学吧
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。