shortest_paths.h revision 1ec681f88b68c6186b267afcce12c7fd667cc9f8
// vim: set cindent
// vim: ts=4 sw=4 et tw=0 wm=0
#include <vector>
using namespace std;
template <class T>
class PairNode;
namespace shortest_paths {
struct Node {
unsigned id;
double d;
Node* p; // predecessor
vector<Node*> neighbours;
vector<double> nweights;
PairNode<Node*>* qnode;
};
inline bool compareNodes(Node *const &u, Node *const &v) {
return u->d < v->d;
}
typedef pair<unsigned,unsigned> Edge;
void floyd_warshall(unsigned n, double** D,
vector<Edge>& es,double* eweights);
void johnsons(unsigned n, double** D,
vector<Edge>& es, double* eweights);
void dijkstra(unsigned s, unsigned n, double* d,
vector<Edge>& es, double* eweights);
}