Dijkstra's Alg. from Paradiam
	Parallel Programming

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#include "diam.h"

#ifdef WEIGHTED
#include "heap.h"

void wdijkstra(int N, edge** A, int* D, int s, int* t, double* d,
               BH h, BHelt* elt, int *pos, double *dist, int *pred)
{
  int i, j, J;
  double od;

  *t = s;    /* current furthest among reachable nodes... */;
  *d = 0.0;  /* and its distance = longest shortest path  */

  for (i=0; i<N; i++) {
    dist[i] = HUGE_VAL;
    pred[i] = -1;
  }

  dist[s] = 0;
  pred[s] = s;

  for (j=0; j<D[s]; j++) {
    J = A[s][j].dest;
    dist[J] = A[s][j].d;
    pred[J] = s;
    elt[J].n = J;
    elt[J].v = dist[J];
    BHinsert(&h, elt[J]);
  }
  
  while (!BHisempty(&h)) {
    i = BHremove_min(&h);
    
    if (dist[i] > *d) {
      *d = dist[i];
      *t = i;
    }
    
    for (j=0; j<D[i]; j++) {
      J = A[i][j].dest;
      od = dist[J];
      if (dist[i] + A[i][j].d < dist[J]) {
        dist[J] = dist[i] + A[i][j].d;
        pred[J] = i;
        if (od == HUGE_VAL) {
          elt[J].n = J;
          elt[J].v = dist[J];
          BHinsert(&h, elt[J]);
        } else {
          BHdecrease(&h, pos[J], dist[J]);
        }
      }
    }

    for (j=0; j<D[i] && A[i][j].dest != pred[i]; j++);
    A[i][j].intree = 1;

    for (j=0; j<D[pred[i]] && A[pred[i]][j].dest != i; j++);
    A[pred[i]][j].intree = 1;
  }
}

#else

void dijkstra(int N, edge** A, int* D, int s, int* t, double* d,
              int *Q, int *dist, int *pred)
{
  int i, j, k, J;
  int Qin=1, Qout=1;

  *t = s;    /* current furthest among reachable nodes... */;
  *d = 0.0;  /* and its distance = longest shortest path  */

  for (i=0; i<N; i++) {
    pred[i] = -1;
  }

  dist[s] = 0;
  pred[s] = s;

  for (i=0; i<D[s]; i++) {
    J = A[s][i].dest;
    dist[J] = 1;
    pred[J] = s;

    A[s][i].intree = 1;
    for (j=0; j<D[J] && A[J][j].dest != s; j++);
    A[J][j].intree = 1;

    Q[Qin++] = J;
  }
  
  while (Qin < N) {

    i = Q[Qout++];
    
    for (j=0; j<D[i]; j++) {
      J = A[i][j].dest;
      if (pred[J] == -1) {
        dist[J] = dist[i] + 1;
        pred[J] = i;
        if (dist[J] > *d) {
          *d = dist[J];
          *t = J;
        }

        A[i][j].intree = 1;
        for (k=0; k<D[J] && A[J][k].dest != i; k++);
        A[J][k].intree = 1;

        Q[Qin++] = J;
      }
    }
  }
}

#endif