Java : Dijkstra's Algorithm

Dijkstra’s Shortest Path Algorithm

  • Dijkstra’s algorithm finds the shortest path in a weighted graph from a single source.
  • The weighted graph for Dijkstra’s algorithm contains only positive edge weights.
  • It uses a priority queue to select a node (vertex) nearest to the source that has not been edge relaxed.
    The edge relaxation for a node is done as below
    If ( distance [ adjacent-node ] > length-of-path-to-adjacent-node-from-current-source + distance [ current-source-node ] ) then
         distance [ adjacent-node ] = length-of-path-to-adjacent-node-from-current-source + distance [ current-source-node ]
    Note :
    a) The distance [ ] array stores the shortest distance of every node from the source-node.
    b) Dijkstra’s algorithm begins by initializing distance [ source ] = 0 i.e the distance from source node to itself is 0 and distance [ all_other_nodes ] = ∞.
  • Since Dijkstra’s algorithm cannot handle negative edge weights, Bellman-Ford algorithm is used for finding the shortest path in a graph containing negative edge weights.
  • In a graph with only positive edge weights, Dijkstra’s algorithm with a priority queue implementation runs faster in O ((E+V) log V) than Bellman-Ford O (E.V).
    E represents the edges and V represents the vertices in the graph.

Algorithm : Dijkstra’s Shortest Path [ Java ]

1.     Initialize the distance from the source node S to all other nodes as infinite (999999999999) and to itself as 0.
2.    Insert an object of < node, distance > for source i.e < S, 0 > in a priority based Queue
       where the priority of the elements in the queue is based on the length of the distance.
3.    While the Priority Queue is not empty do
4.       object_at_top = PriorityQueue. peek();
         Remove the object from the top of the Priority Queue.
         current_source_node = object_at_top . node.
5.       For every adjacent_node to current_source_node do
6.            If ( distance [ adjacent_node ] > length_of_path_to_adjacent_node_from_source + distance [ current_source_node ] ) then
7.                 distance [ adjacent_node ] = length_of_path_to_adjacent_node_from_source + distance [ current_source_node ]
8.                 Update the Priority Queue with the new object < adjacent_node, distance [ adjacent_node ] >

Below data structure is used for storing the graph before applying Dijkstra’s algorithm
Adjacency List : List of pairs of adjacent nodes and their corresponding weights in the graph.

Dijkstras_ShortestPath_DataStructure

Dijkstra’s algorithm step-by-step

This example of Dijkstra’s algorithm finds the shortest distance of all the nodes in the graph from a single / original source node 0.

Step 1 : Initialize the distance of the source node to itself as 0, and ∞ (a very large number) for the rest of the nodes.
             Insert the object < distance_from_original_source, node > in the priority queue.
             i.e Insert < 0, 0 > in the priority queue as the distance from the original source (0) to itself is 0. Dijkstras_Shortest_Path_Step_1

Step 2 : Remove the object < 0, 0 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the original source node ( 0 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
0 1 distance [ 1 ] = ∞ distance [ 1 ] > distance_between [ 0 - 1 ] + distance [ 0 ]
i.e Since ∞ > 5 + 0
Update distance, i.e distance [ 1 ] = 5 and insert object < 1, 5 > in the priority queue.
0 2 distance [ 2 ] = ∞ distance [ 2 ] > distance_between [ 0 - 2 ] + distance [ 0 ]
i.e Since ∞ > 1 + 0
Update distance, i.e distance [ 2 ] = 1 and insert object < 2, 1 > in the priority queue.
0 3 distance [ 3 ] = ∞ distance [ 3 ] > distance_between [ 0 - 3 ] + distance [ 0 ]
i.e Since ∞ > 4 + 0
Update distance, i.e distance [ 3 ] = 4 and insert object < 3, 4 > in the priority queue.

Dijkstras_Shortest_Path_Step_2

Step 3 : Remove the object < 2, 1 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 2 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
2 0 distance [ 0 ] = 0 distance [ 0 ] < distance_between [ 2 - 0 ] + distance [ 2 ]
i.e Since 0 < 1 + 1
No edge relaxation needed.
2 1 distance [ 1 ] = 5 distance [ 1 ] > distance_between [ 2 - 1 ] + distance [ 2 ]
i.e Since 5 > 3 + 1
Update distance, i.e distance [ 1 ] = 4 and insert object < 1, 4 > in the priority queue.
2 3 distance [ 3 ] = 4 distance [ 3 ] > distance_between [ 2 - 3 ] + distance [ 2 ]
i.e Since 4 > 2 + 1
Update distance, i.e distance [ 3 ] = 3 and insert object < 3, 3 > in the priority queue.
2 4 distance [ 4 ] = ∞ distance [ 4 ] > distance_between [ 2 - 4 ] + distance [ 2 ]
i.e Since ∞ > 1 + 1
Update distance, i.e distance [ 4 ] = 2 and insert object < 4, 2 > in the priority queue.

Dijkstras_Shortest_Path_Step_3

Step 4 : Remove the object < 4, 2 > from the from of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 4 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
4 1 distance [ 1 ] = 4 distance [ 1 ] < distance_between [ 4 - 1 ] + distance [ 4 ]
i.e Since 4 < 8 + 2
No edge relaxation needed.
4 2 distance [ 2 ] = 1 distance [ 2 ] < distance_between [ 4 - 2 ] + distance [ 4 ]
i.e Since 1 < 1 + 2
No edge relaxation needed.
4 3 distance [ 3 ] = 3 distance [ 3 ] < distance_between [ 4 - 3 ] + distance [ 4 ]
i.e Since 3 < 2 + 2
No edge relaxation needed.
4 5 distance [ 5 ] = ∞ distance [ 5 ] > distance_between [ 4 - 5 ] + distance [ 4 ]
i.e Since ∞ > 3 + 2
Update distance, i.e distance [ 5 ] = 5 and insert object < 5, 5 > in the priority queue.

Dijkstras_Shortest_Path_Step_4

Step 5 : Remove the object < 3, 3 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 3 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
3 0 distance [ 0 ] = 0 distance [ 0 ] < distance_between [ 3 - 0 ] + distance [ 3 ]
i.e Since 0 < 4 + 3
No edge relaxation needed.
3 2 distance [ 2 ] = 1 distance [ 2 ] < distance_between [ 3 - 2 ] + distance [ 3 ]
i.e Since 1 < 2 + 3
No edge relaxation needed.
3 4 distance [ 4 ] = 2 distance [ 4 ] < distance_between [ 3 - 4 ] + distance [ 3 ]
i.e Since 2 < 2 + 3
No edge relaxation needed.
3 5 distance [ 5 ] = 5 distance [ 5 ] > distance_between [ 3 - 5 ] + distance [ 3 ]
i.e Since 5 > 1 + 3
Update distance, i.e distance [ 5 ] = 4 and insert object < 5, 4 > in the priority queue.

Dijkstras_Shortest_Path_Step_5

Step 6 : Remove the object < 4, 1 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 1 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
1 0 distance [ 0 ] = 0 distance [ 0 ] < distance_between [ 1 - 0 ] + distance [ 1 ]
i.e Since 0 < 5 + 4
No edge relaxation needed.
1 2 distance [ 2 ] = 1 distance [ 2 ] < distance_between [ 1 - 2 ] + distance [ 1 ]
i.e Since 1 < 3 + 4
No edge relaxation needed.
1 4 distance [ 4 ] = 2 distance [ 4 ] < distance_between [ 1 - 4 ] + distance [ 1 ]
i.e Since 2 < 8 + 4
No edge relaxation needed.

Dijkstras_Shortest_Path_Step_6

Step 7 : Remove the object < 4, 5 > from the front of the priority queue and relax the edge going towards every adjacent node(s) from the current source ( 5 ).

Current
source node		 Adjacent
node		 Distance to the adjacent node
from the original source ( 0 )		 Edge relaxation
5 3 distance [ 3 ] = 3 distance [ 3 ] < distance_between [ 5 - 3 ] + distance [ 5 ]
i.e Since 3 < 1 + 4
No edge relaxation needed.
5 4 distance [ 4 ] = 2 distance [ 4 ] < distance_between [ 5 - 4 ] + distance [ 5 ]
i.e Since 2 < 3 + 4
No edge relaxation needed.

The algorithm terminates here as the priority queue is empty and we have calculated the shortest path to all the nodes from the original source 0 as shown below.

Dijkstras_Shortest_Path_Step_7

Data structure used for running Dijkstra’s shortest path : Distance based priority queue for choosing the vertex nearest to the source.
Graph type: Designed for weighted (directed / un-directed) graph containing positve edge weights.
Time complexity of Dijkstra’s algorithm : O ( (E+V) Log(V) ) for an adjacency list implementation of a graph. V is the number of vertices and E is the number of edges in a graph.

Java : Dijkstra’s Shortest Path

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Comparator;

class NodeDist {

    int node; // Adjacent node
    long dist; // Distance to adjacent node

    NodeDist (int node, long dist) {
        this.node = node;
        this.dist = dist;
    }
}

class Dijkstras {

    void ShortestPath (int source_node, int node_count, List<List<NodeDist>> graph) {

        // Assume that the distance from the source_node to other nodes is infinite 
        // in the beginnging, i.e initialize the distance list to a max value
        Long INF = (long) 999999999;
        List<Long> dist = new ArrayList<Long>(Collections.nCopies(node_count, INF));

        // Distance from the source vertex to itself is 0
        dist.set(source_node, (long) 0); // (Node, Dist)

        // Comparator lambda function that enables the priority queue to store the nodes
        // based on the distance in the ascending order.
        Comparator<NodeDist> NodeDistComparator = (obj1, obj2) -> {
            if (obj1.dist < obj2.dist)
                return 1;
            if (obj1.dist > obj2.dist)
                return -1; 
            return 0;
        };

        // Priority queue stores the object node-distance into the queue with 
        // the smallest distance node at the top.
        PriorityQueue<NodeDist> pq = new PriorityQueue<>(NodeDistComparator);

        pq.add(new NodeDist(source_node, 0));

        while (!pq.isEmpty()) {

            NodeDist obj = pq.peek();
            pq.remove();

            int current_source = obj.node;

            for (NodeDist obj_node_dist : graph.get(current_source)) {

                int adj_node = obj_node_dist.node;
                long length_to_adjnode = obj_node_dist.dist;

                // Edge relaxation 
                if (dist.get(adj_node) > length_to_adjnode + dist.get(current_source)) {

                    // If the distance to the adjacent node is not INF, means the object <node, dist> is in the priority queue.
                    // Remove the object before updating it in the priority queue.
                    if (dist.get(adj_node) != INF) {
                        pq.remove(new NodeDist(adj_node, dist.get(adj_node)));
                    }
                    dist.set(adj_node, length_to_adjnode + dist.get(current_source));
                    pq.add(new NodeDist(adj_node, dist.get(adj_node)));
                }
            }
        }

        for (int i=0; i<node_count; i++)
            System.out.println("Source Node(" + source_node + ") -> Destination Node(" + i + ") : " + dist.get(i));
    }

    public static void main(String args[]) {

        int node_count = 6;
        List<List<NodeDist>> graph = new ArrayList<>(node_count);

        for(int i=0; i<node_count; i++) {
            graph.add(new ArrayList<>());
        }

        // Node 0: <1,5> <2,1> <3,4>
        Collections.addAll(graph.get(0), new NodeDist(1, 5), new NodeDist(2, 1), new NodeDist(3, 4));

        // Node 1: <0,5> <2,3> <4,8>
        Collections.addAll(graph.get(1), new NodeDist(0, 5), new NodeDist(2, 3), new NodeDist(4, 8));

        // Node 2: <0,1> <1,3> <3,2> <4,1>
        Collections.addAll(graph.get(2), new NodeDist(0, 1), new NodeDist(1, 3), new NodeDist(3, 2), new NodeDist(4, 1));

        // Node 3: <0,4> <2,2> <4,2> <5,1>
        Collections.addAll(graph.get(3), new NodeDist(0, 4), new NodeDist(2, 2), new NodeDist(4, 2), new NodeDist(5, 1));

        // Node 4: <1,8> <2,1> <3,2> <5,3>
        Collections.addAll(graph.get(4), new NodeDist(1, 8), new NodeDist(2, 1), new NodeDist(3, 2), new NodeDist(5, 3));

        // Node 5: <3,1> <4,3> 
        Collections.addAll(graph.get(5), new NodeDist(3, 1), new NodeDist(4, 3));

        int source_node = 0;
        Dijkstras d = new Dijkstras();
        d.ShortestPath(source_node, node_count, graph);

        System.out.println();
        source_node = 5;
        d.ShortestPath(source_node, node_count, graph);
    }   
}

Output

Source Node(0) -> Destination Node(0) : 0
Source Node(0) -> Destination Node(1) : 4
Source Node(0) -> Destination Node(2) : 1
Source Node(0) -> Destination Node(3) : 3
Source Node(0) -> Destination Node(4) : 2
Source Node(0) -> Destination Node(5) : 4

Source Node(5) -> Destination Node(0) : 4
Source Node(5) -> Destination Node(1) : 6
Source Node(5) -> Destination Node(2) : 3
Source Node(5) -> Destination Node(3) : 1
Source Node(5) -> Destination Node(4) : 3
Source Node(5) -> Destination Node(5) : 0

Copyright (c) 2019-2021, Algotree.org.
All rights reserved.