Graph traversal algorithms

Other graph algorithms

Brute-force algorithms

Test every possible case

Some examples:

Traveling Salesman Problem (TSP)

Find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started.
Solution: derive all possible tours and find the shortest one.

Knapsack Problem

Given n items of weights w1, w2, …, wn and values v1, v2, …, vn and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack.
Solution: generate all possible subsets and calculate the weight to make sure it fits and then calculate the value.
$Ω (2^{n})$

Greedy algorithms

At each step, select the option that is locally the best to find the overall optimal solution.

Example

Activities problem

Given a set of activities with a start time and an end time, find the maximum set of activities that are compatible.
Greedy choice: select the activity with the lowest finish time, in order to maximize the time for remaining activities.

Fractional Knapsack

Similarly to knapsack, there is also a set of items with a certain weight and value, but now you can include a fraction of the item, like 50%.
Greedy choice: select the item with the highest price/weight until there is no more space

Correctness of greedy algorithms

The greedy-choice property

A globally optimal solution that can be arrived at by making a locally optimal (greedy) choice.

The optimal substructure property

An optimal solution to the problem contains within it optimal solutions to subproblems.

Flow algorithms

Max flow

Ford-Fulkerson

Find augmenting path using DFS
Calculate the bottleneck, decrease the capacity and update the residual edges
Repeat until there are no more augmenting paths.
$O (f E)$

Edmonds-Karp

Use BFS to find the shortest path (assume that each edge has a distance of 1)
Then do the same as #Ford-Fulkerson.
$O (V E^{2})$

Maximal bipartite matching

WIP

Minimum Cost Spanning Trees (MST)

Given an undirected connected graph G, a spanning tree is an acyclic subset of the edges that connect all the vertices. The cost of the spanning tree is the sum of the costs of its edges.

A MST has 2 properties:

Cycle property: The heaviest edge along a cycle is never part of an MST
Cut property: Split the vertices of the graph any way you want into two sets A and B, The lightest edge with one endpoint in A and the other in B is always part of an MST.

Kruskal's Algorithm

Start with each vertex as its own cluster.
Pick the lightest edge e
If e connected two vertices in different clusters, e is added to the MST and the clusters are merged
Continue until $V - 1$ edges are added.
$O (E \log V)$

Prim's Algorithm

Start with any vertex and put it in a cluster.
Choose the lightest edge e that is connected to the cluster.
Add the destination vertex to the cluster.
Repeat until all vertices have been added.
$O (E \log V)$

function MST-Prim(G,w,r)
Q = V[G]; // Priority queue Q
foreach u $\in$ Q do // Initialization
key[u] = $\infty$ ;
key[r] = 0;
pred[r] = NIL; // Keep track of tree A
while Q $\neq$ $\emptyset$ do
u = ExtractMin(Q); // Pick the closest unprocessed node
// $\exists$ (u,v) safe and light edge, for tree A
foreach v $\in$ Adj[u] do
if (v $\in$ Q and w(u,v) < key[v]) then // Check if node is not in MST
pred[v] = u;
key[v] = w(u,v); // Min Heap Q is updated!

std::vector<Vertex<T> *> prim(Graph<T> *g) {  
    MutablePriorityQueue<Vertex<T>> q;  
    // First insert all vertices into the queue, with the distance set as infinite (int max).  
    for (Vertex<T> *v: g->getVertexSet()) {  
        v->setDistmax();  
        v->setProcesssing(true);  
        q.insert(v);  
    }    // Set the distance of the first vertex to 0 so that it is used first.  
    vector<Vertex<T> *> res;  
    Vertex<T> *firstVertex = g->getVertexSet()[0];  
    firstVertex->setDist(0);  
    q.decreaseKey(firstVertex);  
  
    // While there are vertices in the queue, extract the one with the lowest distance.  
    while (!q.empty()) {  
        Vertex<T> *vertex = q.extractMin();  
        vertex->setProcesssing(false);  
        res.push_back(vertex);  
        vertex->setVisited(true);  
  
        // For each adjacent vertex, if it is inside the queue and the weight of the edge is lower than the distance, update the path and the distance.  
        for (Edge<T> *edge: vertex->getAdj()) {  
            Vertex<T> *adjacentVertex = edge->getDest();  
            if (adjacentVertex->isProcessing() && edge->getWeight() < adjacentVertex->getDist()) {  
                adjacentVertex->setPath(edge);  
                adjacentVertex->setDist(edge->getWeight());  
                q.decreaseKey(adjacentVertex);  
            }        }    }    return res;  
}

Shortest Path

Dijkstra's Algorithm (SSSP)

Find the shortest path from one vertex to every other vertex

Initialize all vertices with infinite distance except the starting point, which has distance 0.
Create a priority queue to hold the vertices.
While the queue is not empty:
- Extract the head of the queue and add it to the result.
- Relax every outgoing edge:
  - If the neighbor distance is higher than the current distance + the edge distance, update the neighbor distance and its path.

Bellman-Ford-Moore Algorithm (SSSP)

Like #Dijkstra's Algorithm, initialize all vertices with infinite distance except the starting point, which has distance 0.
Relax every outgoing edge for every vertex $V - 1$ times
If there is an iteration where relaxing does not change the distance, the algorithm can stop.
Detect loops by iterating over the vertices one more time and try to relax, if it is possible to relax then there is a negative cycle.
$O (V E)$

Shortest Path in DAG (SSSP)

If the graph is a DAG, then we can calculate the shortest path like this:
Do a topological sorting of the graph.
Like the previous algorithms, initialize all vertices with infinite distance except the starting point, which has distance 0.
Then go over every vertex in topological order and relax every edge.

Johnson's Algorithm (ASSP)

Create a new graph $G^{'}$ by adding an additional source node $s$ .
Run Bellman-Ford on $G^{'}$ . If it returns false, exit the algorithm because there is a negative cycle.
Reweight the edges using $w^{'} (u, v) = w (u, v) + h (u) - h (v)$ . $h (u)$ is the distance to vertex $u$ calculated in the previous step.

Divide & Conquer

The Master Theorem

T (n) = {\begin{cases} d & if n is at most some constant \\ a T (\frac{n}{b}) + f (n) & otherwise \end{cases}

T (n) = {\begin{cases} O (n^{c}) & \log_{b} a < c \\ O (n^{c} \log n) & \log_{b} a = c \\ O (n^{\log_{b} a}) & \log_{b} a > c \end{cases}

$a$ measures how many recursive calls are triggered by each method instance.
$b$ measures the rate of splitting of the input.
$c$ measures the dominating term of the non-recursive work within the recursive method.
$d$ measures the work done in the base case