src/libcola/shortest_paths.cpp

   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 }