program to find the shortest path between any two routers in a given subnet using Dijkstra’s shortest path routing algorithm.

Write a program to find the shortest path between any two routers in a given subnet using Dijkstra’s shortest path routing algorithm.

import java.util.*;

class Dijkstra

{

            int g[][];

            int v, e;

            int d[], p[], vis[];

           

            void CreateGraph()

            {

                        int a, b, w;

                        Scanner is=new Scanner(System. in);

                        System.out.println("Enter the Number of Nodes:");

                        v=is.nextInt();

                        System.out.println("Enter the Number of Edges:");

                        e=is.nextInt();

                        g=new int[v+1][v+1];

                        for(int i=1;i<=v;i++)

                                    for(int j=1;j<=v;j++)

                                                g[i][j]=0;

                                   

                        for(int i=1;i<=e;i++)

                        {

                                    System.out.println("Enter the Edges Info:");

                                    a=is.nextInt();

                                    b=is.nextInt();

                                   

                                    System.out.println("Enter the Weight of these Edges:");

                                    w=is.nextInt();

                                    g[a][b]=g[b][a]=w;

                        }

            }

           

            void CallDij()

            {

                        vis=new int[v+1];

                        d=new int[v+1];

                        p=new int[v+1];

                       

                        for(int i=1;i<=v;i++)

                                    p[i]=vis[i]=0;

                        for(int i=1;i<=v;i++)

                                    d[i]=32767;

                        Dij();

            }

           

            void Dij()

            {

                        int c, cur, min, src, dest;

                        System.out.println("Enter the Source and Destination Vertex:");

                        Scanner is=new Scanner(System.in);

                        src=is.nextInt();

                        dest=is.nextInt();

                        cur=src;

                        vis[cur]=1;

                        d[cur]=0;

                       

                        while(cur!=dest)

                        {

                                    int dc=d[cur];

                                    for(int i=1;i<=v;i++)

                                    {

                                                if(g[cur][i]!=0 && vis[i]!=1)

                                                            if(g[cur][i]+dc<d[i])

                                                            {

                                                                        d[i]=g[cur][i]+dc;

                                                                        p[i]=cur;

                                                            }

                                    }

                                    min=32767;

                                    for(int i=1;i<=v;i++)

                                    {

                                                if(vis[i]!=1 && d[i]<min)

                                                {

                                                            min=d[i];

                                                            cur=i;

                                                }

                                    }

                                    vis[cur]=1;

                        }

                        System.out.println("shortest distance ="+d[dest]);

            }

}

public class Exp2Dijkstra

{

            public static void main(String s[])

            {

                        Dijkstra g=new Dijkstra();

                        g.CreateGraph();

                        g.CallDij();

            }

}

/*Output: -

Microsoft Windows XP [Version 5.1.2600]

(C) Copyright 1985-2001 Microsoft Corp.

C:\Documents and Settings\Sameer Kobal>cd\

C:\>set path="C:\Program Files\Java\jdk1.6.0_17\bin"

C:\>javac Exp2Dijkstra.java

C:\>java Exp2Dijkstra

Enter the Number of Nodes:

5

Enter the Number of Edges:

5

Enter the Edges Info:

1 3

Enter the Weight of these Edges:

10

Enter the Edges Info:

3 5

Enter the Weight of these Edges:

20

Enter the Edges Info:

5 2

Enter the Weight of these Edges:

15

Enter the Edges Info:

2 4

Enter the Weight of these Edges:

9

Enter the Edges Info:

4 1

Enter the Weight of these Edges:

2

Enter the Source and Destination Vertex:

1 5

shortest distance =26

*/