dijkstra

package dijkstra;

import java.util.Scanner;

public class DIJKSTRA
{
    static int MAXNODES = 50;
    static int MAX1 =150;
    static int INFINITY = 5000;

    static int[][] weight=new int[MAXNODES][MAXNODES];
    static int i,j;
    static int[] distance=new int[MAXNODES];
    static int[] visit=new int[MAXNODES];
    static int[] precede=new int[MAXNODES];
    static int itsFinal=0;
    static int[] path=new int[MAX1];
    static int smalldist,newdist,k,s,d,current,n,distcurr;

    static void Display_Result()
    {
        i=d;
        path[itsFinal]=d;
        itsFinal++;
        while(precede[i]!=s)
        {
            j=precede[i];
            i=j;
            path[itsFinal]=i;
            itsFinal++;
        }
        path[itsFinal]=s;
        System.out.format("\nThe shortest path followed is :\n\n");
        for(i=itsFinal; i>0; i--)
        {
            System.out.format("\t\t(%d -> %d) with cost = %d\n\n",path[i],path[i-1],weight[path[i]][path[i-1]]);
        }
        System.out.format("\nFor total cost = %d",distance[d]);
    }

    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        System.out.format("Enter the number of nodes(Less than 50)in the matrix : ");
        n=scanner.nextInt();

        System.out.format("\nEnter the cost matrix :\n\n");
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
                weight[i][j]=scanner.nextInt();
            }
        }
        System.out.format("\nEnter the source node (0 to %d) : ",n-1);

        s=scanner.nextInt();
        System.out.format("\nEnter the destination node (0 to %d) : ",n-1);

        d=scanner.nextInt();
        for(i=0; i<n; i++)
        {
            distance[i]=INFINITY;
            precede[i]=INFINITY;
        }
        distance[s]=0;
        current=s;
        visit[current]=1;
        while(current!=d)
        {
            distcurr=distance[current];
            smalldist=INFINITY;
            for(i=0; i<n; i++)
                if(visit[i]==0)
                {
                    newdist=distcurr+weight[current][i];
                    if(newdist<distance[i])
                    {
                        distance[i]=newdist;
                        precede[i]=current;
                    }
                    if(distance[i]<smalldist)
                    {
                        smalldist=distance[i];
                        k=i;
                    }
                }
            current=k;
            visit[current]=1;
        }
        Display_Result();
    }
}