/* 10(a). W.A.P. to find shortest path from single vertex to all other paths in a digraph (Dijikstra's Algorithm) */

#include<stdio.h>
#include<conio.h>
int n,cnt=1;
void Dijikstra(int a[10][10],int dst,int p[],int d[10],int visited[10])
{
    int i,j,v,u,min;
    for (j = 1; j <= n-1; j++)
    {
        min = 999;
        u = 0;
        for (i = 1; i <= n; i++)
            if ((visited[i] == 0) && (d[i] <= min))
            {    
                min = d[i];
                u = i;
            }
        if (u == dst)
            break;
            visited[u] = 1;
        for (v = 1; v <= n; v++)
            if ((visited[v] == 0) && (d[u] + a[u][v] < d[v]))
            {
                d[v] = d[u] + a[u][v];
                p[v] = u;
            }    
    }
}
void main()
{
    int i,j,u,x[10],a[10][10],src,d[10],s[10],p[10],dst,k;
    clrscr();
    printf("Enter no. of nodes : ");
    scanf("%d",&n);
    printf("\nEnter the cost matrix :\n");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            scanf("%d",&a[i][j]);
            if (a[i][j] == 0)
                a[i][j] = 999;
        }
    printf("\nEnter the source vertex : ");
    scanf("%d",&src);
    for (k = 1; k <= n; k++)
    {
        for (i = 1; i <= n; i++)
        {
            d[i] = a[src][i]; // Initialize array d with the costs
            p[i] = src;
            s[i] = 0; // No vertex selected yet
        }
        s[src] = 1; // Starting from the source vertex
        Dijikstra(a,k,p,d,s);
        if (d[k] == 999)
            printf("\nNo path from %d to %d\n",src,k);
        else
        {
            printf("\n\nShortest distance from %d to %d is %d",src,k,d[k]);
            printf("\nShortest path is :\n");
            i = k;
            while(i != src)
            {
                printf("%d<--",i);
                i = p[i];
             }
             printf("%d",i);
        }
    }
getch();
}
/* OUTPUT
Enter no. of nodes : 3
Enter the cost matrix :
7 0 2
3 8 9
5 4 6
Enter the source vertex : 1

Shortest distance from 1 to 1 is 7
Shortest path is :
1

Shortest distance from 1 to 2 is 6
Shortest path is :
2<--3<--1

Shortest distance from 1 to 3 is 2
Shortest path is :
3<--1
*/