Subscribe to A Kid's scribblings

## Implementing Dijkstra's algorithm

So what is Dijkstra's algorithm ? It is an algorithm to find the shortest possible path from a particular vertex to any other vertex. Now here is the implementation of it using Java.

```package gojabe;
import java.io.*;
public class djkistras_algorithm {
public static void main(String args[])throws Exception
{
System.out.println("No of points to be dealt with ::");
int v[][]=new int[n][n];
int i=0,j=0,k=0;
while(true)
{
System.out.println("Enter the coordinates along with the distances (Pt. A,Pt. B,Distance)::");
if(s.equals("over"))
break;
String data[]=s.split(",");
i=Integer.parseInt(data[0]);
j=Integer.parseInt(data[1]);
k=Integer.parseInt(data[2]);
if(v[i-1][j-1]==0)
{
v[i-1][j-1]=k;
v[j-1][i-1]=k;
}
}
System.out.println("Enter the vertex from which shortest path to all other vertex is goin to be calculated:");
djikstra(v,n,k-1);
}

public static void djikstra(int x[][],int n,int v)
{
int W[][]=new int[n][n];
int dist[]=new int[n];
int i=0,j=0,k=0;
String path[]=new String[n];
W=x;
for(i=0;i<n;i++)
W[i][i]=0;
for(i=0;i<n;i++)
{
if(v==i)
{
dist[v]=0;
path[i]=(v+1)+"->"+(v+1);
}
else if(W[v][i]>0)
{
dist[i]=W[v][i];
path[i]=(v+1)+"->"+(i+1);
}
else
{
path[i]=(v+1)+"";
}
W[i][v]=0;
W[v][i]=0;
}
for(i=0;i<n;i++)
if(dist[i]>0 )
for(j=0;j<n;j++)
{
if(W[i][j]>0){
if(dist[j]==0 && j!=v)
{
dist[j]=dist[i]+W[i][j];
path[j]=path[i]+"->"+(j+1);
}
else if(dist[j]>0 && (dist[i]+W[i][j])<dist[j])
{
dist[j]=dist[i]+W[i][j];
path[j]=path[i]+"->"+(j+1);
}
}
}

display(dist,path,n);
}
public static void display(int dist[],String path[],int n)
{
System.out.println("Stortest possible path::");
for(int i=0;i<n;i++)
System.out.println(path[i]+" = "+dist[i]);
}

}

```

S M T W T F S
12
3456789
10111213141516
17181920 21 2223
24252627282930