Waterbyte - 1 year ago 84
Java Question

# Djikstra's Shortest path algorithm

I am learning Djikstra's and i have prepared the code below based on slightly different idea than Djikstra.
Now, In many of the websites, i have seen the use of Extract min and boolean array of visited edges.
I have used none and my answer is also correct. Is there any test case or scenario where my algo won't work.

``````import java.util.*;
class ShortestPath2
{
static int Ar[][];
static int dist[];

static int nodes;
public static void djikstra(int source)
{
dist[source]=0;

while(!list.isEmpty())
{
source=list.removeFirst();

for(int i=0;i<nodes;i++)
{
if(Ar[source][i]!=0)
{

if(dist[i]>dist[source]+Ar[source][i])
{
dist[i]=Math.min(dist[i],dist[source]+Ar[source][i]);
}

}

}

}

System.out.println(Arrays.toString(dist));
}

public static void main(String[] args)
{

nodes=9;

Ar=new int[nodes][nodes];
dist=new int[nodes];

Arrays.fill(dist,Integer.MAX_VALUE);

Ar=new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};

djikstra(0);

}
}
``````

``````A --100---B --100-- I---100---O  // A-B, B-I, I-O weight : 100