Hybrid Bellman-Ford / Dijkstra

hybridBFD.cc

// Bellman-Ford / DIjkstra hybrid for shortest path
// 
// D. Yefem and I. Rotem (2010):  
// Hybrid Bellman-Ford-Dijkstra Algorithm, 
// TechnicalReport, Ben-Gurion University of the Negev.
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>
#include <algorithm>

using namespace std;

#define ALL(c) c.begin(), c.end()
#define FOR(i,c) for(typeof(c.begin())i=c.begin();i!=c.end();++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define fst first
#define snd second


// === tick a time ===
#include <ctime>
double tick() {
  static clock_t oldtick;
  clock_t newtick = clock();
  double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
  oldtick = newtick;
  return diff;
}


typedef int Weight;
const Weight INF = 99999999;
struct Edge {
  int src, dst;
  Weight weight;
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
bool operator < (Edge e, Edge f) { return e.weight > f.weight; }

bool shortestPath(Graph G, int s, vector<Weight>& dist, vector<int>& prev) {
  int n = G.size();
  dist.assign(n, INF);
  prev.assign(n, -1);
  dist[s] = 0;
  vector<bool> todo(n);
  todo[s] = true;

  REP(epoch, n+2) {
    priority_queue<Edge> Q;
    REP(u, n) if (todo[u])
      Q.push( (Edge){prev[u], u, dist[u]} );
    if (Q.empty()) {
      cout << epoch << endl;
      return true;
    }
    todo.assign(n, false);

    vector<bool> seen(n);
    for (int count = 0; !Q.empty() && count < n; ) {
      Edge e = Q.top(); Q.pop();
      if (seen[e.dst]) continue;
      ++count;
      seen[e.dst] = true;
      FOR(f, G[e.dst]) {
        Weight d = dist[f->src] + f->weight;
        if (dist[f->dst] > d) {
          dist[f->dst] = d;
          prev[f->dst] = f->src;
          todo[f->dst] = true;
          if (!seen[f->dst]) {
            Q.push( (Edge){f->src, f->dst, d} );
          }
        }
      }
    }
  }
  return false;
}

bool shortestPathBF(Graph G, int s, vector<Weight>& dist, vector<int>& prev) {
  int n = G.size();
  dist.assign(n, INF);
  prev.assign(n, -1);
  dist[s] = 0;
  REP(epoch, n+1) {
    bool changed = false;
    REP(u, n) FOR(e, G[u]) {
      Weight d = dist[e->src] + e->weight;
      if (dist[e->dst] > d) {
        dist[e->dst] = d;
        prev[e->dst] = e->src;
        changed = true;
      }
    }
    if (!changed) return true;
  }
  return false;
}

int main() { 
  int n = 32000;
  Graph G(n);
  srand(1);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j) continue;
      double r = 1.0 * rand() / RAND_MAX;
      if (r < 0.999) continue;
      r = 1.0 * rand() / RAND_MAX;
      if (r < 0.999) G[i].push_back( (Edge){i, j, 10} );
      else           G[i].push_back( (Edge){i, j, -1} );
    }
  }
  vector<Weight> dist;
  vector<int> prev;
  tick();
  if (shortestPath(G, 0, dist, prev)) {
    Weight d = 0;
    REP(i, n) d += dist[i];
    cout << d << endl;
  } else {
    cout << "negative cycle" << endl;
  }
  cout << tick() << endl;

  cout << "---" << endl;
  if (shortestPathBF(G, 0, dist, prev)) {
    Weight d = 0;
    REP(i, n) d += dist[i];
    cout << d << endl;
  } else {
    cout << "negative cycle" << endl;
  }
  cout << tick() << endl;
}