finding k shortest paths
in [Theory]
|
From: Steffen on 31 Jul 2006 09:51 Is there any other resource on the topic of finding the k shortest paths in digraph than the one publicized by David Eppstein but using the same algorithm? I read the article "http://citeseer.ifi.unizh.ch/cache/papers/cs/12009/http:zSzzSzwww.ics.uci.eduzSz~eppsteinzSzpubszSzEpp-SJC-99.pdf/eppstein97finding.pdf" but I think I need more "skills" to understand all of the basic algorithm described there. Or, maybe someone can help me understanding it: What is the acyclic graph D(G) and the graph P(G) about? (I would prefer useful examples in this case) Continue hoping to understand, Steffen
From: Steffen on 2 Aug 2006 05:22 While reading again the article mentioned above I wondered about the sample path tree at page 8: Why doesn't have the root of the path tree a child {9}? The edge 9 in G - T obviously has its tail at the path from s to t in T, so I don't know why it is missing there. And a second thing: It is possible to use breadth-first-search in that path tree to get the k shortest pathes? Eppstein means not (page 7), but if we see the path tree as m-heap and use the sum of the delta(e)-values of a node (which is the set sidetracks(p)) as heap-order, then this heap contains as root always the next shortest path. Is that right? Thanks for any help, Steffen
|
Pages: 1 Prev: Greedy Algorithm Next: A Possible "solution" to the Halting Problem |