src/libcola/shortest_paths.h

   1 // vim: set cindent
   2 // vim: ts=4 sw=4 et tw=0 wm=0
   3 #include <vector>
   4 using namespace std;
   5 template <class T>
   6 class PairNode;
   7 namespace shortest_paths {
   8
   9 struct Node {
  10     unsigned id;
  11     double d;
  12     Node* p; // predecessor
  13     vector<Node*> neighbours;
  14     vector<double> nweights;
  15     PairNode<Node*>* qnode;
  16 };
  17 inline bool compareNodes(Node *const &u, Node *const &v) {
  18         return u->d < v->d;
  19 }
  20
  21 typedef pair<unsigned,unsigned> Edge;
  22 void floyd_warshall(unsigned n, double** D,
  23         vector<Edge>& es,double* eweights);
  24 void johnsons(unsigned n, double** D,
  25         vector<Edge>& es, double* eweights);
  26 void dijkstra(unsigned s, unsigned n, double* d,
  27         vector<Edge>& es, double* eweights);
  28 }