ericdrowell/BigOCheatSheet — pull request #13 by qpleple (2013-05-04 16:27:16+00:00)
Title: Added shortest path algorithms (Dijkstra + Bellman-Ford)

The complexity of Dijsktra's algorithm changes according the priority queue implementation. I gave two implementation: Min-heap and Unsorted array. We can't say that one is better than the other:
* in **dense** graph, where |E| = O(|V|), **unsorted array** is better: it gives O(|V|^2) where Min-heap gives O(|V|^2 log n)
* in **sparse** graph, where |E| = O(|V|), **min-heap** is better: it gives O(|V| log |V|) where unsorted array gives O(|V|^2)