Dijkstra algorithm

Write a program to implement the Dijkstra algorithm

Example 1:

Input: n=6,edges={{1,2,10},{2,3,5},{1,3,35},{1,6,50},{2,6,10},{3,4,25},{3,5,5},{4,5,6}},source=1
Output: 0 10 15 26 20 20

Approach:

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.PriorityQueue;

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<HashMap<Integer, Integer>> adj =
                 new ArrayList<HashMap<Integer, Integer>>();
        int n = 7;
        int startEdge = 1;
        // initialization of adj
        for (int i = 0; i < n; i++)
            adj.add(new HashMap<>());

        // make the graph {edge u--v with weight w}
        addEdge(adj, 1, 2, 10);
        addEdge(adj, 2, 3, 5);
        addEdge(adj, 1, 3, 35);
        addEdge(adj, 1, 6, 50);
        addEdge(adj, 2, 6, 10);
        addEdge(adj, 3, 4, 25);
        addEdge(adj, 3, 5, 5);
        addEdge(adj, 4, 5, 6);
        int source = 1;

        int distance[] = dijkstraAlgo(adj, n, source);
        // iterate from start edge to max edge
        System.out.print("Distance is ");
        for (int i = startEdge; i < distance.length; i++) {
            System.out.print(distance[i] + " ");
        }

    }

    private static int[] dijkstraAlgo(ArrayList<HashMap<Integer,
                 Integer>> adj, int n, int source) {
        // priority queue to store the minimum
        // distance node first into the queue
        PriorityQueue<Pair<Integer, Integer>> pq =
                     new PriorityQueue<>();

        // vector to store the distance
        // of all nodes initialize with INT_MAX(infinite)
        int distance[] = new int[n];
        for (int i = 1; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        // push the source into the queue with distance 0
        pq.add(new Pair<Integer, Integer>(0, source));

        // distance of source is 0
        distance[source] = 0;

        // iterate till the end of the
        // queue
        while (!pq.isEmpty()) {
            // current node from the queue
            int curr = pq.peek().getSecond();

            // distance of current node
            int curr_d = pq.peek().getFirst();

            // popped out the current node from the queue
            pq.poll();

            // iterate for all adjacent nodes
            // of the current node
            HashMap<Integer, Integer> map = adj.get(curr);
            for (Integer edge : map.keySet()) {
                // if theie is any update in
                // distance of other nodes
                // then update them
                if (curr_d + map.get(edge) < distance[edge]) {
                    // if the previous distance is
                    // greater then update the new diatance
                    distance[edge] = curr_d + map.get(edge);

                    // push the node into the queue with the
                    // new distance
                    pq.add(new Pair<Integer, Integer>
                        (distance[edge], edge));
                }
            }
        }
        // return the distance vector
        // which holds the distance of all the nodes
        return distance;
    }

    private static void addEdge(ArrayList<HashMap<Integer,
                 Integer>> adj, int u, int v, int w) {
        // undirected graph with weight
        adj.get(u).put(v, w);
        adj.get(v).put(u, w);
    }

}

@SuppressWarnings("rawtypes")
class Pair<F extends Comparable<F>, S extends Comparable<S>> 
            implements Comparable<Pair> {
    private F first;
    private S second;

    public Pair(F first, S second) {
        this.first = first;
        this.second = second;
    }

    public F getFirst() {
        return first;
    }

    public S getSecond() {
        return second;
    }

    @SuppressWarnings("unchecked")
    @Override
    public int compareTo(Pair o) {
        return getFirst().compareTo((F) o.first);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//pair of adjacency list
vector<pair<int,int>> arr[1001];

//function to add the edges
//into the graph
void addEdge(int u,int v,int w)
{
    //undirected graph with weight
    arr[u].push_back({v,w});
    arr[v].push_back({u,w});
}

//dijistras algorithm for sinle source 
//shortes path
vector<int> dijistraAlgorithm(int n,int source)
{
    //proirity queue to store the minimum
    //distance node first into the queue
    priority_queue<pair<int,int>,vector<pair<int,int>>,
                greater<pair<int,int>>> pq;
   
   //vector to store the distance
   //of all nodes initialize with INT_MAX(infinite)
    vector<int> dist(n+1,INT_MAX);
   
    //push the source into the queue with distance
    //0
    pq.push({0,source});
  
    //distance of source is 0
    dist[source]=0;

    //iterate till the end of the
    //queue
    while (!pq.empty())
    {
        //current node from the queue
        int curr=pq.top().second;

         //diatance of current node
        int curr_d=pq.top().first;

        //popped out the current node
        //from the queue
        pq.pop();

        //iterate for all adjacent nodes
        //of the current node
        for(pair<int,int> edge:arr[curr])
         {
             //if theie is any update in
             //distance of other nodes
             //then update them
             if(curr_d+edge.second<dist[edge.first])
              {
                  //if the previous distance is
                  //greater then update the new diatance
                  dist[edge.first]=curr_d+edge.second;

                  //push the node into the queue with the
                  //new distance
                  pq.push({dist[edge.first],edge.first});
              }
         }
    }
 //return the distance vector
 //which holds the diatnce of all
 //the nodes
   return dist;
}
int main()
{
     int n=6;

     //make the graph
     //{edge u--v with weight w}
     addEdge(1,2,10);
     addEdge(2,3,5);
     addEdge(1,3,35);
     addEdge(1,6,50);
     addEdge(2,6,10);
     addEdge(3,4,25);
     addEdge(3,5,5);
     addEdge(4,5,6);

     //souece node 
     int source=1;

     vector<int> distance=dijistraAlgorithm(n,source);
     for(int i=1;i<=n;i++)
       {
           //if the node is not reachable from
           //sourece node then print inf
           if(distance[i]==INT_MAX)
              cout<<"Inf ";
        //else  print the distance
           else
             cout<<distance[i]<<" ";
           
       }
    return 0;
}
//Time Complexity: O(nlog(n)+mlog(n))