Dijkstra Algorithm

shriyanshi24jindal

Mar 29th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 12.18 KB | None | 0 0

copy raw download clone embed print report

class iPair
{
int vertex;
int weight;
iPair(int vertex, int weight)
{
this.vertex = vertex;
this.weight = weight;
}
}
class Pair
{
int node;
int dist;
Pair(int node, int dist)
{
this.node = node;
this.dist = dist;
}
}
class Solution {
public int[] dijkstra(int V, int[][] edges, int src) {
// Step-1 Create an adjacency list
ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
for(int i=0; i<V; i++)
{
adj.add(new ArrayList<iPair>());
}
for(int[] edge : edges)
{
int u = edge[0];
int v = edge[1];
int w = edge[2];
adj.get(u).add(new iPair(v, w));
adj.get(v).add(new iPair(u, w));
}
// Step-2 Create a distance array
int[] distance = new int[V];
Arrays.fill(distance, (int)1e8);
distance[src] = 0;
// Step-3 Create a min-heap <dist, node> to store shortest distance first
PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.dist, y.dist));
pq.offer(new Pair(src, 0));
// Step-4 Process the nodes present in Min-heap using Dijkstra
while(!pq.isEmpty())
{
Pair pair = pq.poll();
int currentNode = pair.node;
int currentDist = pair.dist;
for(iPair adjNode : adj.get(currentNode))
{
int vertex = adjNode.vertex;
int weight = adjNode.weight;
if(distance[currentNode] != (int)1e8 && distance[vertex] > currentDist + weight)
{
distance[vertex] = currentDist + weight;
pq.offer(new Pair(vertex, distance[vertex]));
}
}
}
return distance;
}
}

RAW Paste Data Copied

class iPair
{
    int vertex;
    int weight;
    iPair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Pair
{
    int node;
    int dist;
    Pair(int node, int dist)
    {
        this.node = node;
        this.dist = dist;
    }
}
class Solution {
    public int[] dijkstra(int V, int[][] edges, int src) {
        
        // Step-1 Create an adjacency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<iPair>());
        }
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            
            adj.get(u).add(new iPair(v, w));
            adj.get(v).add(new iPair(u, w));
        }
        
        // Step-2 Create a distance array
        int[] distance = new int[V];
        Arrays.fill(distance, (int)1e8);
        distance[src] = 0;
        
        // Step-3 Create a min-heap <dist, node> to store shortest distance first
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.dist, y.dist));
        pq.offer(new Pair(src, 0));
        
        // Step-4 Process the nodes present in Min-heap using Dijkstra
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.node;
            int currentDist = pair.dist;
            
            for(iPair adjNode : adj.get(currentNode))
            {
                int vertex = adjNode.vertex;
                int weight = adjNode.weight;
                
                if(distance[currentNode] != (int)1e8 && distance[vertex] > currentDist + weight)
                {
                    distance[vertex] = currentDist + weight;
                    pq.offer(new Pair(vertex, distance[vertex]));
                }
            }
        }
        return distance;
    }
}