# Algorithm Runtimes

On studying for my final exam, I found that thinking about the algorithms in a cumulative manner made runtime memorization very simple.

### BFS/DFS

At the simplest level, we have breadth-first search and depth-first search. These two algorithms are true to their name and cycle through the graph in *O(V+E)* time because they cover every edge and every vertex.

#### BFS

#### DFS

### Single Source Shortest Path

**Bellman-Ford’s** runs in *O(VE)* time goes through each vertex *(O(V))* and “relaxes” all edges *(O(E))*.

**Dijstra’s** is (usually) an **improvement** on this and runs in *O(E+Vlg(V))* time. **However**, you need non-negative weights, as this algorithm could get caught in an endless cycle.

*Note: Bellman-Ford can be handy when the shortest path length is known, as you can bound E. In contrast, Dijstra’s would still run in O(E+Vlg(V)) time.*

### All-Pairs Shortest Path

APSP builds on SSSP, but has to additionally look at the shortest path from *EACH* of the edges. So all the runtimes are multiplied by V.

Floyd-Warshall runs in worst case *O(V^3)*.
**Johnson’s Algorithm** takes advantage of **Dijstra’s Algorithm**, and runs it over each vertex.
So, O(V)* O(E+Vlg(V)) = *O(VE + V^2lg(V))*

### Flow Algorithms

Flows are simply graphs with a source and a sink.

**Ford-Fulkerson** goes over each edge a total of f times, since this is the amount of possible residuals.

To bound f, one can run a BFS/DFS to select an optimal residual path to get the **Edmunds-Karp** algorithm, which runs in O(VE^2)

### Helpful Links:

Here is a data structure runtime summary

Here is an algorithm runtime summary

###### *Images taken from wikipedia pages for the respective algorithms. This was written several years back. Port from old webpage.