Talk:Dijkstra's algorithm: Difference between revisions

Revision as of 21:57, 26 May 2011

Revision as of 22:13, 26 May 2011

Line 55:

: 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)) [[User:Kh naba|Kh naba]] ([[User talk:Kh naba|talk]]) 22:13, 26 May 2011 (UTC)