ntddpracticals

Posted by Anonymous on May Thu 3rd 7:16 AM - Never Expires| View : 58
Syntax: TEXT
1551 characters | 114 lines | 1.51 KB
DOWNLOAD | RAW | EMBED | CREATE NEW VERSION OF THIS PASTE | REPORT ABUSE | x
  1. //dijksh
  2.  
  3.  
  4. import java.util.*;
  5.  
  6. class graph
  7. {
  8.  int g[][],d[],visited[],p[];
  9.  int v,e;
  10.  
  11. void creategraph()
  12. {
  13.  int a,b,w;
  14.   Scanner kbd=new Scanner(System.in);
  15.  System.out.println("enter nio v");
  16.  v=kbd.nextInt();
  17.  System.out.println("enterno e");
  18.  e=kbd.nextInt();
  19.  
  20.  g=new int[v+1][v+1];
  21.  
  22.  for (int i=1;i<=v;i++)
  23.   for (int j=1;j<=v;j++)
  24. g[i][j]=0;
  25.  
  26.  
  27.  
  28. for(int i=1;i<=e;i++)
  29. {
  30. System.out.println("enter edge info");
  31.  
  32. a=kbd.nextInt();b=kbd.nextInt();
  33. System.out.println("enter edge wt");
  34. w=kbd.nextInt();
  35. g[a][b]=g[a][b]=w;
  36. }
  37.  
  38.  
  39. }
  40.  
  41. void calldij()
  42. {
  43. visited=new int[v+1];
  44. d=new int[v+1];
  45. p=new int[v+1];
  46.  
  47. for (int i=1;i<=v;i++)
  48. p[i]=visited[i]=0;
  49.  
  50. for (int i=1;i<=v;i++)
  51. d[i]=32767;
  52.  
  53.  
  54. dij();
  55. }
  56.  
  57.  
  58. void dij()
  59. {
  60. int current,c,source,dest,mincost=0;
  61.  
  62. System.out.println("enter souce n destination");
  63.  
  64. Scanner kbd=new Scanner(System.in);
  65. source=kbd.nextInt();
  66. dest=kbd.nextInt();
  67.  
  68. current=source;
  69. visited[current]=1;
  70. d[current]=0;
  71.  
  72.  
  73.  
  74. while(current!=dest)
  75. {
  76. int dc=d[current];
  77. for(int i=1;i<=v;i++)
  78.   {
  79.      if(g[current][i]!=0&&visited[i]!=1)
  80.      if(g[current][i]+dc<d[i])
  81.       {
  82.          d[i]=g[current][i]+dc;
  83.          p[i]=current;
  84.        }
  85.   }
  86. int min=32767;
  87.  
  88. for(int i=1;i<=v;i++)
  89. {
  90.  
  91.   if(visited[i]!=1&&d[i]<min)
  92.   {
  93.  
  94.      min=d[i];
  95.   current=i;
  96. }
  97. }
  98. visited[current]=1;
  99. }
  100.  
  101. System.out.println("shortest dist"+d[dest]);
  102.   }
  103.  }
  104.  
  105. public class dj
  106. {
  107. public static void main(String args[])
  108. {
  109. graph g=new graph();
  110. g.creategraph();
  111. g.calldij();
  112. }
  113. }