// LAB 19 : Dijkstra's Algorithm
/*
Theory: Dijkstra's Algorithm is a graph traversal technique used to find the shortest path from a single source vertex to all other vertices in a weighted graph. It operates by iteratively selecting the vertex with the smallest known distance, updating the distances of its neighbors, and marking it as visited until all vertices have been processed.
*/
//Program:
#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10 
void dijkstra(int G[MAX][MAX],int n,int startnode); 
int main()
{
    int G[MAX][MAX],i,j,n,u;
    printf("Enter no. of vertices:");
    scanf("%d",&n);
    printf("\nEnter the adjacency matrix:\n");    
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        scanf("%d",&G[i][j]);    
    printf("\nEnter the starting node:");
    scanf("%d",&u);
    dijkstra(G,n,u);    
    return 0;
}
 
void dijkstra(int G[MAX][MAX],int n,int startnode)
{ 
    int cost[MAX][MAX],distance[MAX],pred[MAX];
    int visited[MAX],count,mindistance,nextnode,i,j;    
    //pred[] stores the predecessor of each node
    //count gives the number of nodes seen so far
    //create the cost matrix
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(G[i][j]==0)
                cost[i][j]=INFINITY;
            else
                cost[i][j]=G[i][j];
    
    //initialize pred[],distance[] and visited[]
    for(i=0;i<n;i++)
    {
        distance[i]=cost[startnode][i];
        pred[i]=startnode;
        visited[i]=0;
    }    
    distance[startnode]=0;
    visited[startnode]=1;
    count=1;    
    while(count<n-1)
    {
        mindistance=INFINITY;        
        //nextnode gives the node at minimum distance
        for(i=0;i<n;i++)
            if(distance[i]<mindistance&&!visited[i])
            {
                mindistance=distance[i];
                nextnode=i;
            }            
            //check if a better path exists through nextnode            
            visited[nextnode]=1;
            for(i=0;i<n;i++)
                if(!visited[i])
                    if(mindistance+cost[nextnode][i]<distance[i])
                    {
                        distance[i]=mindistance+cost[nextnode][i];
                        pred[i]=nextnode;
                    }
        count++;
    } 
    //print the path and distance of each node
    for(i=0;i<n;i++)
        if(i!=startnode)
        {
            printf("\nDistance of node%d=%d",i,distance[i]);
            printf("\nPath=%d",i);            
            j=i;
            do
            {
                j=pred[j];
                printf("<-%d",j);
            }while(j!=startnode);
    }
}
// Get output PDF at:https://docs.sujan1919.com.np/uploads/ds-lab-19-output.pdf