-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDijkstra algorithm in graph.java
53 lines (53 loc) · 1.83 KB
/
Dijkstra algorithm in graph.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;
public class Main{
public static class Edge{
int destination;
int weight;
public Edge(int destination,int weight){
this.destination=destination;
this.weight=weight;
}
}
public static void dijkstra(ArrayList<ArrayList<Edge>> graph,int start){
int[] distance=new int[graph.size()];
boolean[] visited=new boolean[graph.size()];
PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->Integer.compare(distance[a],distance[b]));
for(int i=0;i<graph.size();i++){
distance[i]=Integer.MAX_VALUE;
}
distance[start]=0;
queue.add(start);
while(!queue.isEmpty()){
int current=queue.poll();
if(visited[current]){
continue;
}
visited[current]=true;
for(Edge e:graph.get(current)){
int neighbor=e.destination;
int newDistance=distance[current]+e.weight;
if(newDistance<distance[neighbor]){
distance[neighbor]=newDistance;
queue.add(neighbor);
}
}
}
for(int i=0;i<graph.size();i++){
System.out.println("Shortest distance from node "+start+"to node "+i+":"+distance[i]);
}
}
public static void main(String[] args){
int numofvertices=5;
ArrayList<ArrayList<Edge>> graph=new ArrayList<>(numofvertices);
for(int i=0;i<numofvertices;i++){
graph.add(new ArrayList<>());
}
graph.get(0).add(new Edge(1,2));
graph.get(1).add(new Edge(2, 5));
graph.get(1).add(new Edge(3, 10));
graph.get(2).add(new Edge(3, 3));
graph.get(3).add(new Edge(4, 7));
int startnode=0;
dijkstra(graph,startnode);
}
}