Friday, August 29, 2014

Dijkstra's Algorithm Implementation in Java

This program implements Dijkstra's algorithm for finding the shortest path to all vertices from the given source in a graph. The code is simple enough. I've added comments wherever necessary.

Graph used in this example:



Code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {

    boolean showMoreInfo = true;
    int distanceFromSource = 0;
    String name;
    public Map<Node, Integer> neighbors = new HashMap<>();

    Node(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Node: ").append(name).append("\n");

        sb.append("Distance from source: ").append(distanceFromSource).append("\n");

        if (showMoreInfo) {
            sb.append("Neighbor nodes: \n");
            for (Node node : neighbors.keySet()) {
                sb.append(node.name).append("  Distance: ").append(this.neighbors.get(node)).append("\n");
            }

            sb.append("\n");
        }
        return sb.toString();
    }
}

public class DijkstrasAlgorithm {
    List<Node> nodes = new ArrayList<>(); 
    
    public void drawGraph() {
        Node s = new Node("s");

        //Two immediate (reachable) neighbors of Node s
        Node t = new Node("t");
        Node y = new Node("y");
        s.neighbors.put(t, 10);
        s.neighbors.put(y, 5);

        //One of the two immediate (reachable) neighbors of Node t
        Node x = new Node("x");
        t.neighbors.put(x, 1);
        t.neighbors.put(y, 2);

        y.neighbors.put(t, 3);
        y.neighbors.put(x, 9);

        //Last Node z (immediately reachable from x and y nodes)
        Node z = new Node("z");
        x.neighbors.put(z, 4);
        y.neighbors.put(z, 2);
        z.neighbors.put(x, 6);
        z.neighbors.put(s, 7);

        //Now add these to List<Node> nodes
        nodes.add(s);
        nodes.add(t);
        nodes.add(y);
        nodes.add(x);
        nodes.add(z);
    }

    private void initializeNodes(){
        for(Node node:nodes)
            node.distanceFromSource = Integer.MAX_VALUE;
        nodes.get(0).distanceFromSource = 0;
    }
    
    private void relax(Node previous, Node next){
        if(next.distanceFromSource>previous.distanceFromSource+previous.neighbors.get(next)){
            next.distanceFromSource = previous.distanceFromSource+previous.neighbors.get(next);
        }
    }
    
    private Node getMin(List<Node> nodes){
        int min = Integer.MAX_VALUE; 
        int minIndex = -1;
        for(int i=0;i<nodes.size();++i){
            if(nodes.get(i).distanceFromSource<min){
                min = nodes.get(i).distanceFromSource; 
                minIndex = i;
            }
        }
        return nodes.get(minIndex);
    }
    
    public void dijkstra(){
        List<Node> nodesCopy = new ArrayList<>();
        nodesCopy.addAll(nodes);
        
        while(!nodesCopy.isEmpty()){
            Node min = getMin(nodesCopy);
            
            Map<Node, Integer> neighbors = min.neighbors;
            for(Map.Entry<Node, Integer> me:neighbors.entrySet()){
                relax(min, me.getKey());
            }
            nodesCopy.remove(min);
        }
    }
    
    public static void main(String[] args){
        DijkstrasAlgorithm da = new DijkstrasAlgorithm();
        da.drawGraph();
        da.initializeNodes(); 
        da.dijkstra();
        
        System.out.println(da.nodes.size());
        for(Node node:da.nodes)
            System.out.println(node);
    }
}

Output:

Node: s
Distance from source: 0
Neighbor nodes:
t  Distance: 10
y  Distance: 5


Node: t
Distance from source: 8
Neighbor nodes:
x  Distance: 1
y  Distance: 2


Node: y
Distance from source: 5
Neighbor nodes:
x  Distance: 9
t  Distance: 3
z  Distance: 2


Node: x
Distance from source: 9
Neighbor nodes:
z  Distance: 4


Node: z
Distance from source: 7
Neighbor nodes:
x  Distance: 6
s  Distance: 7

No comments:

Post a Comment