MCPcopy Create free account
hub / github.com/Tiwarishashwat/InterviewCodes / dijkstra

Method dijkstra

MinimumCosttoConvertStringI.java:2–34  ·  view source on GitHub ↗
(int S, long adj[][])

Source from the content-addressed store, hash-verified

1class Solution {
2 long[] dijkstra(int S, long adj[][]){
3 long dist[] = new long[26];
4 for(int i=0;i<26;i++){
5 dist[i] = Integer.MAX_VALUE;
6 }
7 dist[S] = 0;
8 PriorityQueue<long[]> pq = new PriorityQueue<>(new Comparator<long[]>(){
9 public int compare(long a[], long b[]){
10 if(a[1]<=b[1]){
11 return -1;
12 }
13 return 1;
14 }
15 });
16 pq.offer(new long[] {S,0});
17
18 while(!pq.isEmpty()){
19 long element[] = pq.poll();
20 long node = element[0];
21 long distance = element[1];
22 for(int i=0;i<26;i++){
23 if(adj[(int)node][i]==Integer.MAX_VALUE){
24 continue;
25 }
26 long newDist = distance + adj[(int)node][i];
27 if(newDist<dist[i]){
28 dist[i] = newDist;
29 pq.offer(new long[]{i,newDist});
30 }
31 }
32 }
33 return dist;
34 }
35 public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
36 //adj list for directed graph
37 long adj[][] = new long[26][26];

Callers 1

minimumCostMethod · 0.95

Calls 1

isEmptyMethod · 0.45

Tested by

no test coverage detected