#include <stdio.h>
#include <limits.h>
#include <assert.h>

typedef enum {false, true} bool; /* The order is rather important to
				    get the boolean values right. */
typedef char *string;


#define oo UINT_MAX /* infinity is represented as the maximum unsigned int. */

typedef unsigned int value;

typedef enum { C1, C2, C3, C4, C5, C6, C7, C8, C9, C10, C11, C12, C13, C14, nonexistent} vertex;

const vertex first_vertex = C1;
const vertex last_vertex = C14;

#define no_vertices 14

string name[] = {"C1","C2","C3","C4", "C5", "C6", "C7", "C8", "C9", "C10", "C11", "C12", "C13", "C14"};

value weight[no_vertices][no_vertices] =
 {
/*  C1	C2   C3	  C4    C5   C6   C7  C8   C9  C10  C11 C12  C13  C14 */
  { 0,	10,  oo,  oo,   10,  oo,  oo, oo,  oo,  oo,  oo, oo,  oo,  oo	}, // C1
  { 10,	0,   10,  oo,   10,  10,  oo, oo,  oo,	oo,  oo, oo,  oo,  oo	}, // C2
  { oo,	10,   0,  10,   oo,  10,  10, oo,  oo,	oo,  oo, oo,  oo,  oo	}, // C3
  { oo,	oo,  10,   0,   oo,  oo,  10, oo,  oo,	oo,  oo, oo,  oo,  oo	}, // C4
  { 10,	10,  oo,  oo,    0,  10,  oo, 10,  10,	oo,  oo, oo,  oo,  oo	}, // C5
  { oo,	10,  10,  oo,   10,   0,  10, oo,  10,	10,  oo, oo,  oo,  oo	}, // C6
  { oo,	oo,  10,  10,   oo,  10,   0, oo,  oo,	10,  10, oo,  oo,  oo	}, // C7
  { oo,	oo,  oo,  oo,   10,  oo,  oo,  0,  10,	oo,  oo, 10,  oo,  oo	}, // C8
  { oo,	oo,  oo,  oo,   10,  10,  oo, 10,   0,	10,  oo, 10,  10,  oo	}, // C9
  { oo,	oo,  oo,  oo,   oo,  10,  10, oo,  10,	 0,  10, oo,  10,  10	}, // C10
  { oo,	oo,  oo,  oo,   oo,  oo,  10, oo,  oo,	10,  0,	 oo,  oo,  10	}, // C11
  { oo,	oo,  oo,  oo,   oo,  oo,  oo, 10,  10,	oo,  oo,  0,  10,  oo	}, // C12
  { oo,	oo,  oo,  oo,   oo,  oo,  oo, oo,  10,	10,  oo, 10,   0,  10	}, // C13
  { oo,	oo,  oo,  oo,   oo,  oo,  oo, oo,  oo,	10,  10, oo,  10,   0	}  // C14
};
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * The implementation of Dijkstra's algorithm starts here. *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */


value D[no_vertices];
bool tight[no_vertices];
vertex predecessor[no_vertices];


vertex minimal_nontight() {

  vertex j, u;

  for (j = first_vertex; j <= last_vertex; j++)
     if (!tight[j])
	break;

  assert(j <= last_vertex);

  u = j;

  for (j++; j <= last_vertex; j++)
     if (!tight[j]  &&  D[j] < D[u])
	  u = j;

  return u;
}


bool successor(vertex u, vertex z) {
  return (weight[u][z] != oo  &&  u != z);
}


void dijkstra(vertex s) {
  vertex z, u;
  int i;

  D[s] = 0;

  for (z = first_vertex; z <= last_vertex; z++) {

    if (z != s)
      D[z] = oo;

    tight[z] = false;
    predecessor[z] = nonexistent;
  }

  for (i = 0; i < no_vertices; i++) {

    u = minimal_nontight();
    tight[u] = true;

    if (D[u] == oo)
      continue; /* to next iteration ofthe for loop */

    for (z = first_vertex; z <= last_vertex; z++)
      if (successor(u,z) && !tight[z] && D[u] + weight[u][z] < D[z]) {
	D[z] = D[u] + weight[u][z]; /* Shortcut found. */
	predecessor[z] = u;
      }
  }
}


#define stack_limit 10000 /* Arbitrary choice. Has to be big enough to
			     accomodate the largest path. */

vertex stack[stack_limit];
unsigned int sp = 0; /* Stack pointer. */

void push(vertex u) {
  assert(sp < stack_limit);
  stack[sp] = u;
  sp++;
}

bool stack_empty() {
  return (sp == 0);
}

vertex pop() {
  assert(!stack_empty());
  sp--;
  return stack[sp];
}

/* End of stack digression and back to printing paths. */

void print_shortest_path(vertex origin, vertex destination) {

  vertex v;

  assert(origin != nonexistent  &&  destination != nonexistent);

  dijkstra(origin);

  printf("The shortest path from %s to %s is:\n\n",
	 name[origin], name[destination]);

  for (v = destination; v != origin; v = predecessor[v])
    if (v == nonexistent) {
      printf("nonexistent (because the graph is disconnected).\n");
      return;
    }
    else
      push(v);

  push(origin);

  while (!stack_empty())
    printf(" %s",name[pop()]);

  printf(".\n\n");
}


/* We now run an example. */

int main() {

  print_shortest_path(C1,C14);

  return 0; /* Return gracefully to the caller of the program
	       (provided the assertions above haven't failed). */
}

/* End of program. */