Content deleted Content added
Line 52:
The running time is mentioned as O((|E| + |V|)log |V|) if binary heap is used. I think it assumes Relax(v) = log|V|, but with real binary heap, the operation is "remove v from heap" and "re-add v" are O(|V|) and O(logV), resp., making Relax(v) = O(|V|). Hence, the total running time should be O(|V|log|V| + |E||V|). Can someone verify?
-- [[User:Kh naba|Kh naba]] ([[User talk:Kh naba|talk]]) 21:21, 26 May 2011 (UTC)
: Removing an element from binary heap takes logarithmic time, so the bound in the article is correct. -- [[User:X7q|X7q]] ([[User talk:X7q|talk]]) 21:57, 26 May 2011 (UTC)
:: Removing an element (in this case, a vertex) requires finding it first, which is O(|V|), not O(log|V|) - note: you don't know the index. Relax(v) can alternatively be defined as = find key (O(N)) + decrease-key (O(log V)) = O(|V|) -- [[User:Kh naba|Kh naba]] ([[User talk:Kh naba|talk]]) 22:13, 26 May 2011 (UTC)
| |||