Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from one node to all other nodes in a weighted graph.Its like breadth-first search (BFS), except we use a priority queue instead of a normal first-in-first-out queue. Each item's priority is the cost of reaching it.

Time complexity :

Dijkstra's algorithm using a binary min-heap as a priority queue is O((E+V)logV).
A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected undirected graph. If we assume that the input graph is weakly connected, then the graph must have at least V-1 edges. This implies that V is in O(E), which means we can simplify the running time above to O(ElogV).

Sample Java code :

class pair implements Comparable<pair>{
    int first;
    int second;

    public pair(int a,int b){
        first=a;
        second=b;
    }

    public int compareTo(pair a){
        return this.second - a.second;
    }   
}

class vertex{
    int index;
    int distance;
    int parent;
    Set<pair> adj;

    public vertex(int i){
        index=i;
        distance=Integer.MAX_VALUE;
        parent=i;
        adj=new HashSet<>();
    }
}      

vertex[] arr = new vertex[n+1];
for(int i=1;i<=n;i++)
    arr[i]=new vertex(i);

public shortestPath(){

    PriorityQueue<pair> pq=new PriorityQueue<>();
    arr[1].distance=0;
    pq.add(new pair(1,0));

    while(pq.size()>0){
        pair a=pq.poll();
        for(pair i : arr[a.first].adj){
            if(arr[i.first].distance > a.second+i.second){
                pq.add(new pair(i.first,a.second+i.second));
                arr[i.first].distance=a.second+i.second;
                arr[i.first].parent=a.first;
            }
        }
    }

    if(arr[n].distance==Long.MAX_VALUE) 
        System.out.print(-1);
    else{
        //print shortest path
        ArrayList<Integer> al=new ArrayList<>();
        int a=n;
        while(arr[a].parent!=a){
            al.add(a);
            a=arr[a].parent;
        }
        al.add(a);
        for(int i=al.size()-1;i>=0;i--) 
            System.out.print(al.get(i)+" ");
    }
}