这个图问题的复杂度是多少呢 - 未名空间MITBBS历史存档 | Redian News

国际科技财经博客移民网络热点娱乐民生时事公众号

>Programming - 葵花宝典

>

这个图问题的复杂度是多少呢

这个图问题的复杂度是多少呢# Programming - 葵花宝典

k*f2007-10-18 07:10

1 楼

一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
要求从第一个节点到第n个节点找出k条不同路径
这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
要求k条路径的权重总和最小。
当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
当k＝2以上的时候，好像就不好解了。

e*w2007-10-18 07:10

2 楼

一共就n个节点，怎么才能让k条路“经过的节点都不相同”？

同。

【在 k****f 的大作中提到】

: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。

k*f2007-10-18 07:10

3 楼

有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node

【在 e*****w 的大作中提到】

: 一共就n个节点，怎么才能让k条路“经过的节点都不相同”？
:
: 同。

e*w2007-10-18 07:10

4 楼

i see. 贪心好像不行，貌似有点小难。

【在 k****f 的大作中提到】

: 有些路径只要很少的几个node就可以连接上的，不需要走遍所有的node

s*u2007-10-18 07:10

5 楼

网络流

同。

【在 k****f 的大作中提到】

: 一个图G，有n个节点，有e条边连接节点，每个边有权重 w(i,j)
: 要求从第一个节点到第n个节点找出k条不同路径
: 这k条路径除了在头尾（第一和第n个节点）上有相同节点，其他的经过的节点都不相同。
: 要求k条路径的权重总和最小。
: 当k＝1的时候，就是经典的dijkstra算法。复杂度就是边数
: 当k＝2以上的时候，好像就不好解了。

k*f2007-10-18 07:10

6 楼

关键是有两个路径之间不能有公共的点(除了首尾)，
这个约束处理起来比较麻烦的。

【在 s****u 的大作中提到】

: 网络流
:
: 同。

s*u2007-10-18 07:10

7 楼

一个点拆两个点，容量1，费用0
很常规的处理方法吧

【在 k****f 的大作中提到】

: 关键是有两个路径之间不能有公共的点(除了首尾)，
: 这个约束处理起来比较麻烦的。

k*f2007-10-18 07:10

8 楼

能不能具体说说么？
有k个flow的

【在 s****u 的大作中提到】

: 一个点拆两个点，容量1，费用0
: 很常规的处理方法吧

s*u2007-10-18 07:10

9 楼

每个点V拆成两个点X,Y
除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
最后求一个从源到汇的最小费用最大流

【在 k****f 的大作中提到】

: 能不能具体说说么？
: 有k个flow的

k*f2007-10-18 07:10

10 楼

多谢了！！

【在 s****u 的大作中提到】

: 每个点V拆成两个点X,Y
: 除了源跟汇点，X,Y之间连一条边，容量为1，费用为0
: 如果原图中有边(V,V')，容量C，费用W，新图就(Y,X')连一条边，容量C，费用W
: 对于源点，(X,Y)这条边容量为k，费用为0；汇点同样
: 最后求一个从源到汇的最小费用最大流

s*u2007-10-18 07:10

11 楼

对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-

【在 k****f 的大作中提到】

: 多谢了！！

k*f2007-10-18 07:10

12 楼

呵呵，还在复习network flow算法，
我的问题C刚好是1。

【在 s****u 的大作中提到】

: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-

k*f2007-10-18 07:10

13 楼

顺便再问问
如果题目改成：
k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
能不能用同样的技巧呢？

【在 s****u 的大作中提到】

: 对了，那个C就是1吧，否则大于1不能这样求，因为费用是单位费用 -_-

s*u2007-10-18 07:10

14 楼

同样做法不行吧 -_-
去想想..

【在 k****f 的大作中提到】

: 顺便再问问
: 如果题目改成：
: k个path中最大的权重最小(min max问题)，（原来是要求总和最小, sum）
: 能不能用同样的技巧呢？

热点事件追踪

美国公司裁员Layoff

2024-01-28 18:01

2024-01-09 19:01

2024-01-07 18:01

美国堕胎权争议

2024-01-06 18:01

美国枪击案

2024-01-06 18:01

2023-12-13 17:12

2023-12-02 07:12

2023-11-26 18:11

中美航班重磅消息！每周85班，直飞更方便！

微软、亚马逊、谷歌大裁员！哪些科技和零售公司有缩减规模计划？

中国外长王毅：中美关系已经止跌回稳

脱轨事故造成20多人受伤联邦调查纽约市全部地铁系统

更多 2024-06-26 的新闻