12.6 Complexity analysis

Graph algorithms have potential to be very inefficient if designed carelessly. Consider this naive approach to the shortest path problem from vertex a to b: Try every possible path between a and a, and keep the shortest one. Since a (simple) path is a sequence of edges a\rightarrow\cdots\rightarrow b, every permutation of the vertices forms a potential path (in a complete graph). Even a conservative worst case estimate gives us O(V!) such permutations for a graph with V vertices. This makes the algorithm too slow for any practical application.

For the algorithms we have presented, here is a slightly simplified summary:

• BFS and DFS are linear time in the number of edges of the graph, O(E).
• Dijkstra’s, Prim’s and Kruskal’s are all linearithmic, O(E\log(E)).

Let us look at the reasononing for this, and try to sort out some caveats. All our graph traversal algorithms (DFS, BFS, Dijkstra’s, Prim’s) are on the form:

• Repeat until the agenda is empty:
  • Remove an edge a\rightarrow b from the agenda
  • If b is not visited:
    • Mark b as visited
    • Do something to collect the result
    • Add an item to the agenda, for every outgoing edge of b

We can make the following observations:

• Every directed edge is added to the agenda at most once.
• The visitation check (“if b is not visited”) is performed at most once per edge.
• Every node is added to the visitation set at most once (exactly once if the graph is connected).

In online sources, you often find different answers to the complexity of Dijkstra’s algorithm. This is primarily due to

• Different assumptions about the data structures used for the visitation set, the agenda, and for collecting the result.
• Different optimisations applied to reduce the size of the agenda.
• Different assumptions about the graph, most notably if it is sparse/dense and connected/unconnected.

If the visitation set is an efficient hash table implementation, and vertices have a very good hash function, then initialisation, lookup and adding to the set all take amortised constant time. With these assumptions, the set operations can largely be ignored. In general, the number of edges E will be somewhere between 0 and V^2. If the graph is assumed to be connected (very common for traversal algorithms), then E \geq V-1. If the graph is assumed to be sparse, then E \in O(V). So if the graph is both connected and sparse, V and E are interchangeable. Furthermore, you sometimes see \log(V) and sometimes \log(E). These are in fact interchangeable for all connected graphs, since E \leq V^2 and \log(V^2) \in O(\log V).

With all these caveats in mind, we will look at the algorithms assuming graphs are connected, and that all data structure operations except those on the agenda are O(1). For DFS and BFS, we process every edge by adding them to a stack and queue respectively, so the operations on the agenda are O(1), giving a total complexity of O(E) for both these algorithms.

For Dijkstra’s and Prim’s, the agenda is a priority queue. Adding to and removing from a binary heap is logarithmic in its size, and the size of the agenda is at most E. This gives a total time of O(E\log(E)) for these algorithms, which is the same as O(E\log(V)).

For Kruskal’s algorithm, if we use union-find to detect cycles, the time will be dominated by sorting the edges by weight. This is O(E\log(E)) for an efficient sorting algorithm, giving the algorithm the same time complexity as Prim’s algorithm.