Dijkstra’s algorithm finds the shortest path from a source node to a target node in an undirected or directed graph.

It’s actually a pretty simple algorithm once you break it down properly.

Solution Explanation

It would be fair to summarize the entire solution as “do a breadth-first search of the graph from the source node and as we process each edge, update its target node if we have found a faster path to it with that edge.”

The specific steps in this approach can be implemented as follows:

1. Give all nodes in the graph a value of Integer.MAX_VALUE to indicate they have not been visited.  Also, set their parent node index to -1 to indicate that we haven’t found their parent yet in the shortest path solution.
2. Give the node you are starting from a value of 0.
3. Put all nodes into a minimum priority queue (a data structure that always gives the minimum cost element out next).  The starting node will automatically be the first in the queue as it has value 0.
4. While the queue is not empty:
   • Take the next node N from the queue.
   • If N the target/destination node then we’re done the hard part!  Record that we found the target and break.
   • Otherwise, loop over each edge E in N‘s adjacency list.  We’ll call the node E points to P.
     • If the cost( node N + edge E ) < cost( node P ), then:
       • Set the parent of node P to node N.  This means that we just found a better route from the source to node P.
       • Also, set the new cost of P to cost( node N + edge E ).
       • Also, remove and re-add P to the priority queue as we lowered its cost.  This will change its place in the queue.
5. Assuming we did find the target node earlier, now we just have to print out the results.  To do this, we just start at the target node and follow the parent indexes backwards to the source node (which will still have -1 as its parent).

Implementation

import java.util.*;

public class Dijkstra {

    public static final int V = 5;

    private static class Node {
        int minimumPathCost;
        int node;
        int prev;
    }

    private static class Edge {
        public int weight;
        public int next;
        public Edge(int w, int n) {
            weight = w;
            next = n;
        }
    }

    //Undirected graph, have to add edges in both directions.
    public static void addEdge(List<List<Edge>> graph, int src, int dest, int weight) {
        graph.get(src).add(new Edge(weight, dest));
        graph.get(dest).add(new Edge(weight, src));
    }

    public static List<Integer> dijkstra(List<List<Edge>> graph, int source, int target) {

        //Add all to priority queue
        PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparingInt(o -> o.minimumPathCost));
        Node nodes[] = new Node[V];
        for (int i = 0; i < V; ++i) {
            Node n = new Node();
            n.minimumPathCost = i == source ? 0 : Integer.MAX_VALUE;
            n.node = i;
            n.prev = -1;
            nodes[i] = n;
            q.add(n);
        }

        //While queue not empty, take next node, visit all adjacent
        //nodes, set their minimumPathCost to be this node's minimumPathCost + the cost
        //of getting to the node (if that's less than the current wight).
        //Also, when updating the minimumPathCost, record the source node.
        while (!q.isEmpty()) {
            Node c = q.remove();
            if (c.node == target || c.minimumPathCost == Integer.MAX_VALUE) {
                break;
            }

            for (Edge e : graph.get(c.node)) {
                int newWeight = c.minimumPathCost + e.weight;
                if (newWeight < nodes[e.next].minimumPathCost) {
                    nodes[e.next].minimumPathCost = newWeight;
                    nodes[e.next].prev = c.node;
                    q.remove(nodes[e.next]);
                    q.add(nodes[e.next]);
                }
            }
        }

        //Rebuild the path from the source node to the target node.
        List<Integer> path = new ArrayList<>();
        int current = target;
        while(current != -1) {
            path.add(current);
            current = nodes[current].prev;
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {

        //Build a sample graph. The most efficient
        //solution from 0 ->4 is [0 -> 2 -> 3 -> 4].
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < V; ++i) {
            graph.add(new ArrayList<>());
        }
        addEdge(graph, 0, 2, 2);
        addEdge(graph, 0, 1, 18);
        addEdge(graph, 1, 3, 1);
        addEdge(graph, 2, 3, 3);
        addEdge(graph, 2, 4, 9);
        addEdge(graph, 3, 4, 1);

        //Execute the algorithm and print the solution path.
        System.out.println(dijkstra(graph, 0, 4));
    }
}