#include <limits.h>

#define INFINITY    INT_MAX     /* value for infty        */

typedef int AdjacencyTable[MAXVERTEX][MAXVERTEX];
 
typedef int DistanceTable[MAXVERTEX];

int n;                  /* number of vertices in the graph  */
 
AdjacencyTable cost;    /* describes the graph              */
 
DistanceTable D;        /* shortest distances from vertex 0 */
 
/* Distance: calculates the cost of the shortest path.

 
Pre:  A directed graph is given which has n vertices
by the weights given in the table cost.
Post: The function finds the shortest path from vertex
0 to each vertex of the graph and returns the path that it
finds in the array D.
 */
 
void Distance(int n, AdjacencyTable cost, DistanceTable D)
{

    Boolean final[MAXVERTEX];   /* Has the distance from 0 to v been found? */
                               /* final[v] is true iff v is in the set S.  */
    int i;          /* repetition count for the main loop               */
                           /* One distance is finalized on each pass through the loop.         */
    int w;          /* a vertex not yet added to the set S              */
    int v;          /* vertex with minimum tentative distance in D[]*/
    int min;        /* distance of v, equals D[v]                 */

    final[0] = TRUE;        /* Initialize with vertex 0 alone in the set S. */
    D[0] = 0;

    for (v = 1; v < n; v++) {
        final[v] = FALSE;
        D[v] = cost[0][v];
    }

    /* Start the main loop; add one vertex v to S on each pass.   */
    for (i = 1; i < n; i++) {
        min = INFINITY;     /* Find the closest vertex v to vertex 0. */
        for (w = 1; w < n; w++)
            if (!final[w])
                if (D[w] < min) {
                    v = w;
                    min = D[w];
                }
        final[v] = TRUE;            /* Add v to the set S.    */
        for (w = 1; w < n; w++)     /* Update the remaining distances in D.   */
            if (!final[w])
                if (min + cost[v][w] < D[w])
                    D[w] = min + cost[v][w];
    }
}