Dijkstra's Algorithm Programming in C

Tweet

# include
# define size 20
# define P 1
# define T 0
# define infinity 9999

typedef struct Label
{
    int predecessor;
    int length;
    int flag;
}lb;
int k, min, count;
lb state[size];
int visit_path[size];
int Short_Path(int a[size][size], int , int , int,
int path [size], int *);
void Input(int , int a[size][size]);
void Output(int , int a[size][size]);
int  Short_Path(int a[size][size], int n, int s, int t,
int path[size], int *dist)
{
    int i;
    int t1, t2;
    *dist = 0;

    for(i = 1; i <= n; i ++)
    {
        state[i].predecessor = 0;
        state[i].length = infinity ;
        state[i].flag = T;
    }
    state[s].predecessor = 0;
    state[s].length = 0;
    state[s].flag = P;
    k = s;
    do
    {
        for ( i = 1; i <= n; i++)
        {
            if ((a[k][i] > 0) && (state[i].flag == T))
            {
                if ((state[k].length + a[k][i]) < state[i].length)
                {
                    state[i].predecessor = k;
                    state[i].length = state[k].length + a[k][i];
                }
            }
        }
        min = infinity;
        k = 0;
        for ( i =1; i <= n; i++)
        {
            if ((state[i].flag == T) && (state[i].length < min))
            {
                min = state[i].length;
                k = i;
            }
        }
        if ( k==0)
            return (0);
        state[k].flag = P;
    } while(k != t);

    k = t;
    count = 1;
    do
    {
        visit_path[count] = k;
        count ++;
        k = state[k].predecessor;
    } while(k!= 0);
    count --;
    for ( i = 1; i <= count ; i++)
        path[i] = visit_path[count-i+1];
    for ( i = 1; i < count ; i ++)
    {
        t1 = path[i];
        t2 = path [i+1];
        *dist += a[t1][t2];
    }
    return (count);
}
void Input(int n, int a[size][size])
{
    int i, j;
    printf("\n Input adjacency matrix \n");
    for(i =0; i < n; i++)
    {
        for(j =0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
        printf("\n");
    }
}
void Output(int n, int a[size][size])
{
    int i, j;
    printf("\n Adjacency matrix \n");
    for(i =0; i < n; i++)
    {
        for(j =0; j < n; j++)
        {
            printf("  %d", a[i][j]);
        }
        printf("\n");
    }
}
main()
{
    int a[size][size];
    int path [size];
    int org, dest, dist;
    int count, i, n;
    printf("\n Input the number of vertices in the graph: ");
    scanf("%d", &n);
    Input(n,a);
    Output(n,a);
    printf("\n Input strating vertex: ");
    scanf("%d", &org);
    printf("\n Input destination: ");
    scanf("%d", &dest);
    count = Short_Path(a, n, org, dest, path, &dist);
    if (dist)
    {
        printf("\n Shortest path: %d", path[1]);
        for (i = 2; i<=count; i++);
        printf(" => %d", path[i]);
        printf("\n Minimum distance = %i", dist);
    }
    else
        printf("\n Path does not exist \n");
}

Posted in: Graphs