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 {
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 }
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 }