Question: Write a program to find shortest path from your home to college using Dijkstra’s
algorithm.
Code:
Code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Dijkstras {
static class vertex{
int distance;
boolean visited;
int no;
int previous;
@Override public String toString() {
return "vertex{" +
"distance=" + distance +
", visited=" + visited +
", no=" + (no+1) +
", previous=" + (previous+1) +
'}';
}
public vertex(int distance, boolean visited, int no, int previous) {
this.distance = distance;
this.visited = visited;
this.no = no;
this.previous = previous;
}
}
public static void main(String[] nt){
ArrayList<vertex> arrayList=new ArrayList<>();
ArrayList<vertex> result=new ArrayList<>();
/* int graph[][] = 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} }; */ int[][] graph={{0,4,8,0,0},{0,0,5,8,10},{0,4,0,0,3},{0,0,0,0,6},{0,0,0,7,0}};
for (int i=0;i<graph.length;i++){
arrayList.add(new vertex(Integer.MAX_VALUE,false,i,Integer.MAX_VALUE));
}
arrayList.get(0).distance=0;
arrayList.get(0).previous=0;
Comparator<vertex> com=new Comparator<vertex>() {
@Override public int compare(vertex vertex, vertex t1) {
return vertex.distance-t1.distance;
}
};
vertex poped;
while (arrayList.size()!=0){
Collections.sort(arrayList,com);
poped=arrayList.get(0);
arrayList.remove(0);
if(poped.visited==false){
for (int i=0;i<graph[poped.no].length;i++){
if(graph[poped.no][i]!=0&& find(arrayList,i)!=Integer.MAX_VALUE){
int x=find(arrayList,i);
if(graph[poped.no][i]+poped.distance<arrayList.get(x).distance){
arrayList.get(x).distance=graph[poped.no][i]+poped.distance;
arrayList.get(x).previous=poped.no;
}
}
}
poped.visited=true;
result.add(poped);
}
}
Comparator<vertex>comp2=new Comparator<vertex>() {
@Override public int compare(vertex vertex, vertex t1) {
return vertex.no-t1.no;
}
};
Collections.sort(result,comp2);
for(int i=0;i<result.size();i++){
System.out.println(result.get(i).toString());
}
}
static int find(ArrayList<vertex> arrayList,int n){
int i=Integer.MAX_VALUE;
for (int x=0;x<arrayList.size();x++){
if(arrayList.get(x).no==n){
return x;
}
}
return i;
}
}
Output:
