复习1

Pseudo-codes are from wikipedia

1.Dijkstra

Example

struct Point{int v, int w;}
class Comp {
    bool operator() (Point a, Point b) const {
        return a.w > b.w;
    }
}
...
vector<vector<pair<int, int>>> g;
...
dis[start] = 0;
priority_queue<int, vector<int>, Comp> q;
q.push({start, 0});
set<int> vis;
while (!q.empty() && vis.size() != V) {
    int u = q.top();
    vis.insert(u);
    q.pop();
    for (int i = g[u][0]; i < g[u].size(); i++) {
        int v = g[u][i].first;
        int w = g[u][i].second;
        if (dis[u] + w < dis[v]) {
            dis[v] = dis[u] + w;
            q.push({v, w});
        }
    }
}
return dis[end];

1. Prim

   Example

   // similar to dijkstra implementation
   vector<int> keys(V, 0); // shortest edge to each node
   ...
   set<pair<int, int>> mst;
   while (!q.empty() && vis.size() != V) {
       int u = q.top();
       q.pop();
       vis.insert(u);
       for (int i = g[u][0]; i < g[u].size(); i++) {
           int v = g[u][i].first;
           int w = g[u][i].second;
           if (key[v] > w) {
               key[v] = w;
               mst.insert(make_pair(u, v));
               q.push(v);
           }
       }
   }
   

2. Kruskal

   Example

   // Disjoint set
   fa[V];
   int find(int x){
       if(x == fa[x]) return x 
       else return fa[x] = find(fa[x])
   }
   ...
   sort edges according to the weights.
   ...
   int i = 0;
   while (i < E && e < V - 1) {
       Edge edge = edges[i++];
   	int fau = find(u);
   	int fav = find(v);
       if (fau != fav) {
           fa[fau] = fav;
           mst.insert(edge);
       	e++;
       } 
   }
   

3. Floyd Warshell

   dis[V][V] = {inf};
   ...
   for every pair of points
       dis[u][v] = w[u][v]  // the weight of the edge (u,v)
   for each v
       dis[v][v] = 0 
   for k from 1 to V		// path going through k
       for i from 1 to V
          for j from 1 to V
             if (dist[i][j] > dist[i][k] + dist[k][j])
                dist[i][j] = dist[i][k] + dist[k][j]
   

4. Bellman-ford

   for each vertex v:
      distance[v] = inf             
      predecessor[v] = null         
      distance[source] = 0   
             
   for i from 1 to V-1:
   	for each edge:
   		if distance[u] + w < distance[v]:
   			distance[v] = distance[u] + w
               predecessor[v] = u
      
             
   for each edge:
   	if distance[u] + w < distance[v]:
   		// Negative cycle
      
   return distance[], predecessor[]
   

5. SPFA

   set dis to inf
   ...
   dis[0] = 0
   set<int> inq;
   queue<int> q;    
   q.push(s);
   while (!q.empty()) {
       int u = q.front();
       q.pop();
       for (int i = g[u][0]; i < g[u].size(); i++) {
           int v = g[u][i].first;
           int w = g[u][i].second;
           if (dis[u] + w < dis[v]) {
               dis[v] = dis[u] + w;
               if (!inq.count(v)) {
                   q.push(v);
               }
           }
       }
   }
   

6. Construct a heap

   • Build-head algorithm: from array_size/2 -> 0, do heapify(push down)
   • Push_down: adjust the ordering
   • Push_up: adjust the ordering between the current node and its parent
   • Insert: add to back of the array, push up
   • Delete: move the last to the front, push down