/* Solution: All Roads Lead... */
/* E. Jason Riedy, ejr@cise.ufl.edu */
/*
  I suspect that many people will use a straight {depth,bredth}-first
  search.  The graph is small enough that this is computationally
  possible, but it's definately not the fastest.

  Dijkstra's algorithm for computing the entire tree of shortest paths
  from one node is simple and fast.  It works by picking the closest
  node and the updating all the unreached nodes' distances.  The
  update, known as relaxing an edge, checks the far endpoint's current
  distance.  If the new one is less, it replaces the old one. 

  The only complications with Dijkstra's algorithm come from the
  associated data structure.  Here I use a simple heap.  The
  relaxation step must be followed by a heap-property check.
*/

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<ctype.h>

enum { MAX_NODES = 30, MAX_EDGES = 100, INF = 10000, NIL = -1 };

/*----------------------------------------------------------------------*/

struct _graph {
  int N;
  int xadj[MAX_NODES + 1];
  int adjncy[MAX_EDGES];
  int cost[MAX_EDGES];
};

typedef struct _graph graph;

/*----------------------------------------------------------------------*/
/* Graph maintenance routines used in edge_io().  */

int find_edge( graph* g, int from, int to )
{
  int i;

  for (i = g->xadj[from]; i < g->xadj[from+1]; i++)
    if (to == g->adjncy[i])
      return i;
  return NIL;
}

void add_edge( graph* g, int from, int to, int w )
{
  int n_to_shift;
  int i;

  n_to_shift = g->xadj[g->N] - g->xadj[from + 1];
  /* Eh, I'm lazy.  Didn't feel like typing more loops... */
  memmove (
	   &g->adjncy[g->xadj[from + 1] + 1],
	   &g->adjncy[g->xadj[from + 1]],
	   n_to_shift * sizeof(int));
  memmove (
	   &g->cost[g->xadj[from + 1] + 1],
	   &g->cost[g->xadj[from + 1]],
	   n_to_shift * sizeof(int));
  
  g->adjncy[g->xadj[from + 1]] = to;
  g->cost[g->xadj[from + 1]] = w;

  for (i = from + 1; i <= g->N; i++)
    g->xadj[i]++;
}

void change_edge( graph* g, int from, int to, int w )
{
  int i = find_edge (g, from, to);

  if (NIL == i)
    return add_edge (g, from, to, w);

  g->cost[i] = w;
}

void delete_edge( graph* g, int from, int to )
{
  int i = find_edge (g, from, to);

  if (NIL == i)
    return;

  g->cost[i] = INF;
}

/*----------------------------------------------------------------------*/

/* 
  The simplest reasonable structure for storing the nodes is a minimum
  heap.  It allows simple extraction of the least node (O(log n)), and
  decreasing (relaxing) keys is also fairly simple (also O(\log n)).

  A minimum heap is just a complete tree where any node's key is smaller
  than the keys contained in either child tree.  Because it is a complete
  tree, a heap can be stored in an array.  The left and right child of
  node i are at 2i and 2i+1, respectively.  */

/* Make sure i and all it's children obey the heap property. */
void heapify( int N, int* heap, int* back_ptr, int* dist, int i )
{
  int left = 2*i;
  int right = left+1;
  int smallest;
  int tmp;

  if (right < N && dist[heap[right]] < dist[heap[i]])
    smallest = right;
  else if (left < N && dist[heap[left]] < dist[heap[i]])
    smallest = left;
  else
    return;  /* i is the smallest */

  tmp = heap[i];
  heap[i] = heap[smallest];
  heap[smallest] = tmp;

  back_ptr[heap[i]] = i;
  back_ptr[heap[smallest]] = smallest;

  /* 
     Recurse on the node which was modified.  This could
     be flattened into a loop, and the compiler probably
     will do that, but the recursive solution is prettier,
     IMHO.
  */
  heapify (N, heap, back_ptr, dist, smallest);
}

void build_heap( int N, int* heap, int* back_ptr, int* dist )
{
  int i;

  /* 
     This starts at the first internal node and proceeds to heapify 
     everything.
  */

  for (i = N/2; i > 0; i--)
    heapify (N, heap, back_ptr, dist, i);
}

int extract_min( int* N, int* heap, int* back_ptr, int* dist )
{
  int out;

  if (*N < 1) 
    return NIL;
    
  out = heap[1];

  heap[1] = heap[*N];          /* Move the last to the first,         */
  back_ptr[heap[1]] = 1;
  --*N;                        /* then make the heap one smaller, and */
  heapify (*N, heap, back_ptr, dist, 1); 
                               /* restore the heap property.          */

  return out;
}

void decrease_key( int N, int* heap, int* back_ptr, int* dist, int i )
{
  int parent = i/2;
  int tmp;

  if (parent < 1)
    return;

  if (dist[heap[i]] > dist[heap[parent]])  /* check the heap property */
    return;

  /* If it's violated, swap with parent and recurse... */
  /* 
     This traces the route from the modified node to the root
     until the heap property is again valid.
  */

  tmp = heap[i];
  heap[i] = heap[parent];
  heap[parent] = tmp;

  back_ptr[heap[i]] = i;
  back_ptr[heap[parent]] = parent;
  decrease_key( N, heap, back_ptr, dist, parent );
}

/* Just a debugging routine... */
void print_heap( int N, int* heap, int* dist, int i, int depth )
{
  int j;

  if (i > N)
    return;

  for (j = 0; j < depth; j++) putchar('.');
  printf("%d, %d (%d)\n", heap[i], dist[heap[i]], i);
  print_heap( N, heap, dist, 2*i, depth + 1);
  print_heap( N, heap, dist, 2*i+1, depth + 1);
}

/*----------------------------------------------------------------------*/

/*
  Relaxing a node checks to see if the new distance is shorter
  than the previously known one.
*/
void relax( int* dist, int* parent, int from, int to, int cost )
{
  /*
  printf("relax: %d (%d) %d (%d) %d\n", dist[from], from, dist[to], to, cost);
  /* More debugging stuff */

  if (dist[to] <= dist[from] + cost)
    return;

  dist[to] = dist[from] + cost;
  parent[to] = from;
}

void dijkstra_shortest_path( graph* g, int start, int* dist, int* parent )
{
  int curr;
  int prev = NIL;

  int N = g->N;
  int heap[MAX_NODES + 1];
  int back_ptr[MAX_NODES];
  int i;

  /* initialization */
  for (i = 0; i < N; i++) {
    dist[i] = 10*INF;
     /* ran into strange buglet with size of INF, so make it larger here... */
    parent[i] = NIL;
  }
  dist[start] = 0;

  for (i = 0; i < N; i++) {
    heap[i + 1] = i;
    back_ptr[i] = i+1;
  }
  build_heap( N, heap, back_ptr, dist );

  /* Now greedily choose the next node and examine all its neighbors. */
  while (N > 0) {
    curr = extract_min (&N, heap, back_ptr, dist);

    /*
    printf("current: %d\n", curr);
    /**/

    for (i = g->xadj[curr]; i < g->xadj[curr + 1]; i++) {
      /*
      printf(" -- Examining edge %d->%d, %d\n", curr, g->adjncy[i],
	     g->cost[i]);
      /**/

      relax (dist, parent, curr, g->adjncy[i], g->cost[i]);
      /* might have changed the key, so... */
      decrease_key (N, heap, back_ptr, dist, back_ptr[g->adjncy[i]]);
    }
  }
}

/*----------------------------------------------------------------------*/
/* The rest is standard stuff.  */

void print_path( int start, int end, int* parent, int* dist )
{
  int path[MAX_NODES];
  int i;
  int curr;

  /* Trace the backwards path into an array, then print it. */
  i = 0;
  for (curr = end; curr != start; curr = parent[curr])
    path[i++] = curr + 1;
  path[i++] = curr + 1;

  printf("The shortest path from %d to %d has length %d and\nfollows ",
	 start + 1, end + 1, dist[end]);

  for (--i; i > 0; --i)
    printf("%d -> ", path[i]);
  printf("%d.\n", path[i]);
}

void edge_io( graph* g )
{
  char op;
  int from, to, w;

  for (;;) {
    printf("(C)hange, (D)elete, (E)nd: ");
    scanf(" %c", &op);
    
    switch (tolower(op)) {
      case 'c':
	printf ("Enter origin, endpoint, and cost: ");
	scanf ("%d %d %d", &from, &to, &w);
	change_edge (g, from - 1, to - 1, w);
	break;
      case 'd':
	printf ("Enter origin and endpoint: ");
	scanf ("%d %d", &from, &to);
	delete_edge (g, from - 1, to - 1);
	break;
      case 'e':
	return;
      default:
	printf("[Not an operation.]\n");
    }
  }
}

int original_N = 9;
int original_xadj[] =
{
  0, 2, 5, 7, 10, 14, 17, 19, 22, 24
};
int original_adjncy[] =
{
  1, 3,
  0, 2, 4,
  1, 5,
  0, 4, 6,
  1, 3, 5, 7,
  2, 4, 8,
  3, 7,
  4, 6, 8,
  5, 7
};
int original_cost[] =
{
  3, 2,
  3, 6, 7,
  6, 5,
  2, 8, 1,
  7, 8, 3, 4,
  5, 3, 2,
  1, 9,
  4, 9, 6,
  2, 6
};

void init_graph( graph* g )
{
  int i;

  g->N = original_N;
  for (i = 0; i <= original_N; i++)
    g->xadj[i] = original_xadj[i];
  for (i = 0; i < g->xadj[g->N]; i++) {
    g->adjncy[i] = original_adjncy[i];
    g->cost[i] = original_cost[i];
  }
}

void main(void) 
{
  graph g;

  int dist[MAX_NODES + 1];
  int parent[MAX_NODES + 1];

  int start, end;

  init_graph(&g);

  edge_io(&g);

  for (;;) {
    printf ("\nFind a path from where to where? ");
    scanf ("%d %d", &start, &end);
    if (feof(stdin))
      break;
    start--; end--;

    dijkstra_shortest_path ( &g, start, dist, parent );
    print_path (start, end, parent, dist);
  }
  putchar('\n');
}