1 // vim: set cindent
2 // vim: ts=4 sw=4 et tw=0 wm=0
3 #include "shortest_paths.h"
4 #include <float.h>
5 #include <cassert>
6 #include <iostream>
7 #include <libvpsc/pairingheap/PairingHeap.h>
8 using namespace std;
9 namespace shortest_paths {
10 // O(n^3) time. Slow, but fool proof. Use for testing.
11 void floyd_warshall(
12 unsigned n,
13 double** D,
14 vector<Edge>& es,
15 double* eweights)
16 {
17 for(unsigned i=0;i<n;i++) {
18 for(unsigned j=0;j<n;j++) {
19 if(i==j) D[i][j]=0;
20 else D[i][j]=DBL_MAX;
21 }
22 }
23 for(unsigned i=0;i<es.size();i++) {
24 unsigned u=es[i].first, v=es[i].second;
25 assert(u<n&&v<n);
26 D[u][v]=D[v][u]=eweights[i];
27 }
28 for(unsigned k=0; k<n; k++) {
29 for(unsigned i=0; i<n; i++) {
30 for(unsigned j=0; j<n; j++) {
31 D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
32 }
33 }
34 }
35 }
36 void dijkstra_init(Node* vs, vector<Edge>& es, double* eweights) {
37 for(unsigned i=0;i<es.size();i++) {
38 unsigned u=es[i].first, v=es[i].second;
39 vs[u].neighbours.push_back(&vs[v]);
40 vs[u].nweights.push_back(eweights[i]);
41 vs[v].neighbours.push_back(&vs[u]);
42 vs[v].nweights.push_back(eweights[i]);
43 }
44 }
45 void dijkstra(
46 unsigned s,
47 unsigned n,
48 Node* vs,
49 double* d)
50 {
51 assert(s<n);
52 for(unsigned i=0;i<n;i++) {
53 vs[i].id=i;
54 vs[i].d=DBL_MAX;
55 vs[i].p=NULL;
56 }
57 vs[s].d=0;
58 PairingHeap<Node*> Q(&compareNodes);
59 for(unsigned i=0;i<n;i++) {
60 vs[i].qnode = Q.insert(&vs[i]);
61 }
62 while(!Q.isEmpty()) {
63 Node *u=Q.extractMin();
64 d[u->id]=u->d;
65 for(unsigned i=0;i<u->neighbours.size();i++) {
66 Node *v=u->neighbours[i];
67 double w=u->nweights[i];
68 if(v->d>u->d+w) {
69 v->p=u;
70 v->d=u->d+w;
71 Q.decreaseKey(v->qnode,v);
72 }
73 }
74 }
75 }
76 void dijkstra(
77 unsigned s,
78 unsigned n,
79 double* d,
80 vector<Edge>& es,
81 double* eweights)
82 {
83 assert(s<n);
84 Node vs[n];
85 dijkstra_init(vs,es,eweights);
86 dijkstra(s,n,vs,d);
87 }
88 void johnsons(
89 unsigned n,
90 double** D,
91 vector<Edge>& es,
92 double* eweights)
93 {
94 Node vs[n];
95 dijkstra_init(vs,es,eweights);
96 for(unsigned k=0;k<n;k++) {
97 dijkstra(k,n,vs,D[k]);
98 }
99 }
100 }