☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月24日20:59:28 星期二)
提到：
路径的点可以重复。
是加一维吗？
dijkstra加一维，什么时候确定一个点的前k短路永久化了呢？
floyd改进算法要求是n^3*k的
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月25日00:15:31 星期三 提到：
dijkstra 可以的
floyd 不可以，以前 valla 有一道经典的错题的
【 在 hotsaucetang (sillybird100) 的大作中提到: 】
: 路径的点可以重复。
: 是加一维吗？
: dijkstra加一维，什么时候确定一个点的前k短路永久化了呢？
:
: floyd改进算法要求是n^3*k的
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月25日01:39:49 星期三)
提到：
guys, that's what i am doing now, hehe...
1. yes, dijkstra, just keep very vertex popped at most k times.
2. for floyd, another idea gonna work
change the equation
a[i, j] = min { a[i, j], a[i, l] + a[l, j] }
to be
\vec{a}[i, j] = k-merge (\vec{a}[i,j], k-sel (\vec{a}[i,l] \times \vec{a}[l,j]
))
\vec{a}[i,j] is the (sorted) k-best list for a[i,j]
\times means sth. like "crossproduct", basically you have k for both \vec{a}[i
,l] and \vec{a}[l,j]
so you have k^2 possibilities, and k-sel selects the top k among them
k-merge is like merging two sorted arrays, but just output the top k.
this is going to be O(n^3 * k \log k) (using heap for selection)
do you agree?
【 在 dwyak 的大作中提到: 】
: dijkstra 可以的
: floyd 不可以，以前 valla 有一道经典的错题的
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月25日11:52:06 星期三 提到：
how can you solve the k-sel in O(k \log k)?
there are k^2 possibilities, and i can only solve it in O(k^2).
【 在 blhuang (Pascal de chine) 的大作中提到: 】
: guys, that's what i am doing now, hehe...
: 1. yes, dijkstra, just keep very vertex popped at most k times.
: 2. for floyd, another idea gonna work
: change the equation
: a[i, j] = min { a[i, j], a[i, l] + a[l, j] }
: to be
: \vec{a}[i, j] = k-merge (\vec{a}[i,j], k-sel (\vec{a}[i,l] \times \vec{a}[l,j]
: ))
:
: \vec{a}[i,j] is the (sorted) k-best list for a[i,j]
: .................（以下省略）
☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月25日21:38:48 星期三)
提到：
i don't know it too. how can u solve it in O(klogk)
and i still don't know the improvement about dijkstra.
if you keep very vertex poped at most k times, when will you set a vertex to b
e "certain"?
just choose one which has the min-k-pathes currently to expand and mark it to
be fixed?
i don't think this is right
【 在 dwyak 的大作中提到: 】
: how can you solve the k-sel in O(k \log k)?
: there are k^2 possibilities, and i can only solve it in O(k^2).
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月25日23:18:19 星期三 提到：
just treat one vertice as k vertex.
now there are n * k vertex in the new graph, while the number of edges is n
* k^2.
【 在 hotsaucetang (sillybird100) 的大作中提到: 】
: i don't know it too. how can u solve it in O(klogk)
: and i still don't know the improvement about dijkstra.
: if you keep very vertex poped at most k times, when will you set a vertex to b
: e "certain"?
: just choose one which has the min-k-pathes currently to expand and mark it to
: be fixed?
: i don't think this is right
: .................（以下省略）
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月26日04:53:59 星期四)
提到：
hahahah: you got the point.
then how to do O(k \log k) instead of O(k^2) is
a recent invention of mine (no no, a year ago).
i have a paper for this.
but the idea is very simple, so i dunno if i am the first to get it.
【 在 dwyak 的大作中提到: 】
: how can you solve the k-sel in O(k \log k)?
: there are k^2 possibilities, and i can only solve it in O(k^2).
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月26日04:54:20 星期四)
提到：
why n k^2 edges?
【 在 dwyak 的大作中提到: 】
: just treat one vertice as k vertex.
: now there are n * k vertex in the new graph, while the number of edges is ..
: * k^2.
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月26日12:15:17 星期四 提到：
oh.. n^2 * k edges
【 在 blhuang (Pascal de chine) 的大作中提到: 】
: why n k^2 edges?
☆──────────────────────────────────────☆
dynamic (searching for direction) 于 2004年02月26日15:09:07 星期四 提到：
【 在 dwyak (下次一定要爬头) 的大作中提到: 】
: just treat one vertice as k vertex.
~~~~~~~vertex~~~~~~vertices:P
: now there are n * k vertex in the new graph, while the number of edges is n
: * k^2.
: .................（以下省略）
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月26日18:52:27 星期四 提到：
:P
【 在 dynamic (searching for direction) 的大作中提到: 】
: ~~~~~~~vertex~~~~~~vertices:P
☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月26日20:00:30 星期四)
提到：
why is n^2*k... i can't understand
why not m*k?
【 在 dwyak 的大作中提到: 】
: oh.. n^2 * k edges
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月26日20:41:14 星期四 提到：
yes, m*k, n^2*k is the upperbound
【 在 hotsaucetang (sillybird100) 的大作中提到: 】
: why is n^2*k... i can't understand
: why not m*k?
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月27日11:31:49 星期五 提到：
hehe, i know how to solve the k-sel in O(k \log k) now.
it's really simple.
【 在 blhuang (Pascal de chine) 的大作中提到: 】
: hahahah: you got the point.
: then how to do O(k \log k) instead of O(k^2) is
: a recent invention of mine (no no, a year ago).
: i have a paper for this.
:
: but the idea is very simple, so i dunno if i am the first to get it.
☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月27日19:14:51 星期五)
提到：
i still can't understand.
if there are m*k edges, then how to make this graph?
how to guarantee that you will get the first kth min pathes instead of k minim
um pathes of one vertex?
【 在 dwyak 的大作中提到: 】
: yes, m*k, n^2*k is the upperbound
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月28日02:07:18 星期六)
提到：
i am not sure either.
dwy pls give some detail
【 在 hotsaucetang 的大作中提到: 】
: i still can't understand.
: if there are m*k edges, then how to make this graph?
: how to guarantee that you will get the first kth min pathes instead of k m..
: um pathes of one vertex?
☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月28日16:28:03 星期六)
提到：
i know it too now.
but i don't know whether our methods are the same one.
i use a k-element heap
【 在 dwyak 的大作中提到: 】
: hehe, i know how to solve the k-sel in O(k \log k) now.
: it's really simple.
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月28日16:48:44 星期六)
提到：
sure
【 在 hotsaucetang 的大作中提到: 】
: i know it too now.
: but i don't know whether our methods are the same one.
: i use a k-element heap
☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月28日16:54:16 星期六)
提到：
but this is only an O(n^3*klogk) algorithm
my book says that there is an O(n^3*k) method
do you know that?
【 在 blhuang 的大作中提到: 】
: sure
☆──────────────────────────────────────☆
tenshi (tenshi) 于 2004年02月28日21:59:43 星期六 提到：
there are algorithms much better than (k*n^3)
【 在 hotsaucetang (sillybird100) 的大作中提到: 】
: but this is only an O(n^3*klogk) algorithm
: my book says that there is an O(n^3*k) method
: do you know that?
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月28日22:16:47 星期六 提到：
you can treat all the edges from (u,i) to (v,1), (v,2), ..., (v,k) as a
single edge.
【 在 hotsaucetang (sillybird100) 的大作中提到: 】
: i still can't understand.
: if there are m*k edges, then how to make this graph?
: how to guarantee that you will get the first kth min pathes instead of k minim
: um pathes of one vertex?
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月29日01:03:23 星期天)
提到：
a lot of papers on this topic
see Eppstein, 97 for example
【 在 hotsaucetang 的大作中提到: 】
: but this is only an O(n^3*klogk) algorithm
: my book says that there is an O(n^3*k) method
: do you know that?
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月29日01:04:18 星期天)
提到：
yeah
【 在 tenshi 的大作中提到: 】
: there are algorithms much better than (k*n^3)
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月29日01:06:39 星期天)
提到：
still not sure
for each edge in the original graph,
you split it to k edges?
how?
【 在 dwyak 的大作中提到: 】
: you can treat all the edges from (u,i) to (v,1), (v,2), ..., (v,k) as a
: single edge.
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月29日01:48:05 星期天 提到：
for each vertex in the original graph, split it to k vertices.
and for each vertex (v,i) in the new graph, there will be at most n edges
linked to it, because we needn't link (v,i) to every (u,j) (1 <= j <= k). a
single edge for (v,i) & all the (u,j) is enough.
this algo is simple, but not quite efficient. it's only O(m * k * \log (n * k)), but easy to code.
【 在 blhuang (Pascal de chine) 的大作中提到: 】
: still not sure
: for each edge in the original graph,
: you split it to k edges?
: how?
☆──────────────────────────────────────☆
blhuang (Pascal de chine) 于 2004年02月29日13:29:46 星期天)
提到：
in your algo.
is the shortest path (in the new graph) to (v,i)
the i-th best path (in the original graph) to v?
how do you ensure this?
【 在 dwyak 的大作中提到: 】
: for each vertex in the original graph, split it to k vertices.
: and for each vertex (v,i) in the new graph, there will be at most n edges
: linked to it, because we needn't link (v,i) to every (u,j) (1 <= j <= k). ..
: single edge for (v,i) & all the (u,j) is enough.
: this algo is simple, but not quite efficient. it's only O(m * k * \log (n ..
☆──────────────────────────────────────☆
hotsaucetang (sillybird100) 于 2004年02月29日20:33:35 星期天)
提到：
i don't know it either!
and how to find the thesis you mentioned above, blhuang?
【 在 blhuang 的大作中提到: 】
: in your algo.
: is the shortest path (in the new graph) to (v,i)
: the i-th best path (in the original graph) to v?
: how do you ensure this?
☆──────────────────────────────────────☆
dwyak (下次一定要爬头) 于 2004年02月29日23:05:45 星期天 提到：
yes, (v,i) is the i-th best path from the source to v.
this algo is just based on the dijkstra algo, so it's obviously correct.
【 在 blhuang (Pascal de chine) 的大作中提到: 】
: in your algo.
: is the shortest path (in the new graph) to (v,i)
: the i-th best path (in the original graph) to v?
: how do you ensure this?
: .................（以下省略）
gmail.com
|