Download The write up here
Dijkstra.java
import java.util.*;public class Dijkstra
{
public int distance[] = new int[10];
public int cost[][] = new int[10][10];
public void calc(int n,int s)
{
int flag[] = new int[n+1];
int i,minpos=1,k,c,minimum;
for(i=1;i<=n;i++)
{
flag[i]=0;
this.distance[i]=this.cost[s][i];
}
c=2;
while(c<=n)
{
minimum=99;
for(k=1;k<=n;k++)
{
if(this.distance[k]<minimum && flag[k]!=1)
{
minimum=this.distance[i];
minpos=k;
}
}
flag[minpos]=1;
c++;
for(k=1;k<=n;k++)
{
if(this.distance[minpos]+this.cost[minpos][k] < this.distance[k] && flag[k]!=1 )
this.distance[k]=this.distance[minpos]+this.cost[minpos][k];
}
}
}
public static void main(String args[])
{
int nodes,source,i,j;
Scanner in = new Scanner(System.in);
System.out.println("Enter the Number of Nodes \n");
nodes = in.nextInt();
Dijkstra d = new Dijkstra();
System.out.println("Enter the Cost Matrix Weights: \n");
for(i=1;i<=nodes;i++)
for(j=1;j<=nodes;j++)
{
d.cost[i][j]=in.nextInt();
if(d.cost[i][j]==0)
d.cost[i][j]=999;
}
System.out.println("Enter the Source Vertex :\n");
source=in.nextInt();
d.calc(nodes,source);
System.out.println("The Shortest Path from Source \t"+source+"\t to all other vertices are : \n");
for(i=1;i<=nodes;i++)
if(i!=source)
System.out.println("source :"+source+"\t destination :"+i+"\t MinCost is :"+d.distance[i]+"\t");
}
}
/*OUTPUT
iotlab@iotlab-Veriton-M200-B360:~$ javac Dijkstra.java
iotlab@iotlab-Veriton-M200-B360:~$ java Dijkstra
Enter the Number of Nodes
5
Enter the Cost Matrix Weights:
0 1 0 2 0
1 0 1 0 4
0 1 0 0 3
2 0 0 0 3
0 4 3 3 0
Enter the Source Vertex :
1
The Shortest Path from Source 1 to all other vertices are :
source :1 destination :2 MinCost is :1
source :1 destination :3 MinCost is :2
source :1 destination :4 MinCost is :2
source :1 destination :5 MinCost is :5
*/
No comments:
Post a Comment