src/libcola/shortest_paths.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// vim: set cindent 
// vim: ts=4 sw=4 et tw=0 wm=0
#include <vector>

template <class T>
class PairNode;
namespace shortest_paths {

struct Node {
    unsigned id;
    double d;
    Node *p; // predecessor    
    std::vector<Node*> neighbours;
    std::vector<double> nweights;
    PairNode<Node*> *qnode;
};
inline bool compareNodes(Node *const &u, Node *const &v) {
    return u->d < v->d;
}

typedef std::pair<unsigned,unsigned> Edge;

void floyd_warshall(unsigned n, double** D,
        std::vector<Edge>& es,double* eweights); 

void johnsons(unsigned n, double** D,
        std::vector<Edge>& es, double* eweights);

void dijkstra(unsigned s, unsigned n, double* d, 
        std::vector<Edge>& es, double* eweights);
}