请教一个算法题关于shortest path的 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Programming - 葵花宝典

请教一个算法题关于shortest path的

请教一个算法题关于shortest path的# Programming - 葵花宝典

n*n2013-04-04 07:04

1 楼

北京税务部门明确表示，自然人股东将在公司上市前取得的股权在公司上市后进行转让
的，必须按照《个人所得税法》的相关规定缴纳20%的个人所得税。

v*n2013-04-04 07:04

2 楼

有做塑料粒子（颗粒）的吗，各种类型请报价

T*S2013-04-04 07:04

3 楼

"师尊在叫我？"这名叫奉志的老者，迟疑的问了一句，生怕自己听错了。
“叫你过来，犹豫什么，这位前辈有事情要问你。你原来不是居住此地的吗？”儒生却
生怕自己这位徒弟行动迟缓，惹得韩立不快，口气蓦然严厉了起来。
“是，弟子这就过来。”确定自己没有听错后，这位筑基期老者只能硬着头皮飞了过去
，来到了儒生旁边。
“你原先居住在这地方的？”韩立目光在奉志身上扫了几眼，神色一动下，缓缓问道。
“启禀前辈，晚辈在入门之前，的确祖居此地的。”筑基期老者恭谨的回道，一点不敢
隐瞒。
“祖居此地，你如何筑基的？”韩立点点头，随后大出人意意料的问出一句让所有人一
怔的话来。
“晚辈是家母昔年遇到一位前辈高人，赠送了一枚筑基丹，才得以顺利筑基的。”奉志
心中奇怪，但口中急忙回道。
“这么说，你就是小梅的后人了。”韩立神色略缓了下来。
“小梅，前辈说是莫非是在下外祖母，难道前辈就是赠送筑基丹的那位前辈。”奉志先
是一呆，随即想起什么的失声起来。
“你还不笨，倒也能猜得出来。”韩立嘿嘿一笑。
“多谢前辈当年的赠丹大恩。晚辈一直铭记在心的。”这筑基老者满脸惊喜地急忙虚空
拜了下去。
儒生和那黑肤老者却听得有些发怔了

g*32013-04-04 07:04

4 楼

你定义了什么是美
你定义了什么是胖
什么是正常
什么是道德
什么是荣耀
什么是成功
什么是聪慧
什么是这个年龄该做的事
什么是应该分享的故事和照片
什么时候该笑和哭
什么时候shit和have sex
但是，你不是我
所以
fuck it

w*u2013-04-04 07:04

5 楼

版上牛多，特来请教
1. 给定一个有向图，边是有非负权重的，找最短路径，这个简单，用Dijkstra算法
2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是有且只隔了一个点
）不能同时出现在path中，这时候最短路径如何求？
约束条件比如 n2不能和n5同时出现在路径中
n1----n2---n4---n5---n7
| | |
|-----n3----|---n6----|

n*a2013-04-04 07:04

6 楼

啊哦

g*g2013-04-04 07:04

7 楼

这不是很简单，分别去掉n2和n5求最短路径就完了。

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

: 版上牛多，特来请教
: 1. 给定一个有向图，边是有非负权重的，找最短路径，这个简单，用Dijkstra算法
: 2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是有且只隔了一个点
: ）不能同时出现在path中，这时候最短路径如何求？
: 约束条件比如 n2不能和n5同时出现在路径中
: n1----n2---n4---n5---n7
: | | |
: |-----n3----|---n6----|

T*P2013-04-04 07:04

8 楼

orz.

【在 n******n 的大作中提到】

: 北京税务部门明确表示，自然人股东将在公司上市前取得的股权在公司上市后进行转让
: 的，必须按照《个人所得税法》的相关规定缴纳20%的个人所得税。

w*u2013-04-04 07:04

9 楼

思路不错，问题在于如果有好几组这样的节点限制，如果操作阿？
如果n3和n6不能放在一起
如果图大一点，限制数多一点，恐怕不行哦

【在 g*****g 的大作中提到】

: 这不是很简单，分别去掉n2和n5求最短路径就完了。

n*n2013-04-04 07:04

10 楼

泡泡的小非要被盘剥了。

【在 T*P 的大作中提到】

: orz.

s*n2013-04-04 07:04

11 楼

最短路径的实质是动态变成如果有约束条件不能使用公开人员的四有结果的话,我上的
问题可能就是运动车多少是时间解决的

版上牛多，特来请教1. 给定一个有向图，边是有非负权重的，找最短路径，这个简单
，用Dijkstra算法2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是
有且只隔了........

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

: 思路不错，问题在于如果有好几组这样的节点限制，如果操作阿？
: 如果n3和n6不能放在一起
: 如果图大一点，限制数多一点，恐怕不行哦

p*22013-04-04 07:04

12 楼

DFS就可以了吧？

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

w*u2013-04-04 07:04

13 楼

能具体说说么？

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

: 最短路径的实质是动态变成如果有约束条件不能使用公开人员的四有结果的话,我上的
: 问题可能就是运动车多少是时间解决的
:
: 版上牛多，特来请教1. 给定一个有向图，边是有非负权重的，找最短路径，这个简单
: ，用Dijkstra算法2. 如果带有约束条件，如果某两个点（这两个点不是相邻店，而是
: 有且只隔了........

w*u2013-04-04 07:04

14 楼

DFS 应该是不行的

【在 p*****2 的大作中提到】

:
: DFS就可以了吧？

p*22013-04-04 07:04

15 楼

为什么不行？

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

: DFS 应该是不行的

k*g2013-04-04 07:04

16 楼

好像是正解.
A shortest path from n0 (starting point) to ny (any point) can be classified
as:
n0 ... ... ny (not touching any constrained point), OR
n0 ... n2 ... ny (touching only n2), OR
n0 ... n5 ... ny (touching only n5), OR
... (more combinations if there are additional constrains)
The best result from the first class is simply computed by removing all
constrained points from the graph.
For each of the remaining classes, the search can be broken down into:
(e.g. for the class that allows n2, rejects n5)
Find shortest path from n0 to n2;
Find shortest path from n2 to ny;
Compare the sum (n0 ... n2, n2 ... ny) with the sum (n0 ... ny) and keep
the better result.
Likewise for other cases.
To speed up search, the Dijkstra algorithm will be run multiple times, each
time using a constrain point as origin. That is, it will be run with n0 as
origin;, then re-run with n2 as origin; then re-run with n5 as origin; and
so on.

【在 g*****g 的大作中提到】

: 这不是很简单，分别去掉n2和n5求最短路径就完了。

w*u2013-04-04 07:04

17 楼

如果n3 和n6也是constraints，
碰巧，n0...n2 ...ny 中包含n3 和 n6
n0...n5 ...ny 中包含n3 和 n6,
而且当iter n3或者n6的时候，都包含n2 和n5, 那这个算法就不适合了吧

classified

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

:
: 好像是正解.
: A shortest path from n0 (starting point) to ny (any point) can be classified
: as:
: n0 ... ... ny (not touching any constrained point), OR
: n0 ... n2 ... ny (touching only n2), OR
: n0 ... n5 ... ny (touching only n5), OR
: ... (more combinations if there are additional constrains)
: The best result from the first class is simply computed by removing all
: constrained points from the graph.

s*n2013-04-04 07:04

18 楼

最短路径算法是dynamic programming。就是用sub-optimal solution递归的算。
如果最优解不是有两个sub 最优解构成，那么不能用DP.
例如，TSp问题就是NPC的。你举得例子的极端情况。
那么只有指数时间复杂度的naive algo可以用了。例如bfs,dfs.

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

: 能具体说说么？