Content deleted Content added
Line 76:
::::: Here's one source which talks about this idea: [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#dijkstra3]. They further eliminate space disadvantage you mentioned by using a balanced tree (standard in C++) which does everything heaps can do plus an efficient find operation (if you know key's priority). -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 20:54, 28 May 2011 (UTC)
:::::: @X7q: That's also an interesting approach. However, I see that "find" in the balanced-tree using the priority key could be risky because there can potentially be vertexes with same priority (you want to decrease-key your current vertex, not any vertex with same priority). I believe that's reason why this may not be a reliable choice. -- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 12:06, 31 May 2011 (UTC)
::::::: We use (priority, vertex number) pairs as keys in the tree, not just priorities.
::::: @David: That approach is so useful for implementers, I would hazard "citation needed" and still mention it. Ideally, it could be described so that it's trivially logical, so as not to require external proof/citation. For example, as long as it is explained that priority of a vertex only reduces and never increases, and that the queue "does not care" about duplicate entries since old priorities are still intact for older entries for it to function correctly, then I think it can survive. It's a tip most people will easily miss (or re-invent) if not mentioned. Let me put this tip in article (with ref. to you, of course) and see if it survives scrutiny :). -- [[User:Kh naba|Naba Kumar]] ([[User talk:Kh naba|talk]]) 11:41, 31 May 2011 (UTC)
| |||