Back to Basics - Dijkstra's Algorithm

See http://en.wikipedia.org/wiki/Dijkstra's_algorithm for reference.

Vertex Class

package weighted.graph;

public class Vertex {
    String name;
    public Vertex(String name) {
        this.name = name;
    }
    
    public String getName() {
        return name;
    }
}

Code Formatted by ToGoTutor

Graph Class: Use a HashSet for unordered vertices.

package weighted.graph;

import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;

public class Graph {
    Map<Vertex, HashSet<Vertex>> edgeMap = new LinkedHashMap<Vertex, HashSet<Vertex>>();
    Map<Vertex, LinkedHashMap<Vertex, Integer>> edgeWeightMap = new LinkedHashMap<Vertex, LinkedHashMap<Vertex, Integer>>();
    
    public HashSet<Vertex> adjacentEdges(Vertex v) {
        HashSet<Vertex> set = edgeMap.get(v);
        if(set == null) {
            return new HashSet<Vertex>();
        } else {
            return set;
        }
    } 
    
    public void connectVertices(Vertex v1, Vertex v2, Integer weight) {
        addVertexToSet(v1, v2, weight);
        addVertexToSet(v2, v1, weight);
    }
    
    public Integer getWeight(Vertex v1, Vertex v2) {
        return edgeWeightMap.get(v1).get(v2);
    }
    
    private void addVertexToSet(Vertex v1, Vertex v2, Integer weight) {
        HashSet<Vertex> set1 = edgeMap.get(v1);
        if(set1 == null) {
            set1 = new HashSet<Vertex>();
            edgeMap.put(v1, set1);
            LinkedHashMap<Vertex, Integer> weightMap = new LinkedHashMap<Vertex, Integer>();
            edgeWeightMap.put(v1, weightMap);
        }
        if(!set1.contains(v2)) {
            set1.add(v2);
            LinkedHashMap<Vertex, Integer> weightMap = edgeWeightMap.get(v1);
            weightMap.put(v2, weight);
        }
    }
}

Code Formatted by ToGoTutor

Main: This algorithm moves outward from the starting node. This creates a n-surface, which represents n steps away from the original node. Vertices are not processed on the n-surface when the distance to the vertex is greater than the current minimum distance to the new node.

package weighted.graph;

import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Map;

// http://en.wikipedia.org/wiki/Dijkstra's_algorithm
public class Main {
    public static void main (String[] args) {
        Vertex five = new Vertex("Five");
        Vertex six = new Vertex("Six");
        Vertex three = new Vertex("Three");
        Vertex four = new Vertex("Four");
        Vertex one = new Vertex("One");
        Vertex two = new Vertex("Two");
        
        Graph graph = new Graph();
        graph.connectVertices(five, six, 9);
        graph.connectVertices(five, four, 6);
        graph.connectVertices(six, three, 2);
        graph.connectVertices(four, three, 11);
        graph.connectVertices(six, one, 14);
        graph.connectVertices(three, one, 9);
        graph.connectVertices(three, two, 10);
        graph.connectVertices(four, two, 15);
        graph.connectVertices(one, two, 7);
        
        SP(graph, five, three);
        SP(graph, five, two);
    }

    private static void SP(Graph graph, Vertex v1, Vertex v2) {
        HashSet<Vertex> surface = new HashSet<Vertex>();
        surface.add(v1);
        
        HashSet<Vertex> processed = new HashSet<Vertex>();
        processed.add(v1);
        
        Map<Vertex, Integer> distMap = new LinkedHashMap<Vertex, Integer>();
        distMap.put(v1, 0);
        
        HashSet<Vertex> nextSurface = new HashSet<Vertex>();
        
        while(!surface.isEmpty()) { // Done
            Object[] objects = surface.toArray();
            for(Object object: objects) {
                Vertex surV = (Vertex) object;
                processed.add(surV);
                Integer surVDist = distMap.get(surV);
                HashSet<Vertex> edges = graph.adjacentEdges(surV);
                Integer currentV2Dist = distMap.get(v2);
                if (currentV2Dist == null || surVDist < distMap.get(v2)) {
                    for(Vertex nextSurV: edges) {
                        if(!processed.contains(nextSurV)) {
                            //System.out.println("v1:"+surV.getName()+" v2:"+nextSurV.getName());
                            processVertex(graph, distMap, nextSurface, surVDist, surV, nextSurV);
                        }
                    }
                }
            }
            surface = nextSurface;
            nextSurface = new HashSet<Vertex>();
        }
        System.out.println("Complete");
    }

    private static void processVertex(Graph g, Map<Vertex, Integer> distMap, HashSet<Vertex> nextSurface, Integer surVDist, Vertex a, Vertex b) {
        Integer nextSurVCurrentDist = distMap.get(b);
        Integer nextSurVProposedDist = surVDist+g.getWeight(a,  b);
        if(nextSurVCurrentDist == null) {
            nextSurface.add(b);
            System.out.println("Node:"+b.getName()+" Dist:"+nextSurVProposedDist);
            distMap.put(b, nextSurVProposedDist);
        } else if (nextSurVProposedDist < nextSurVCurrentDist) {
            System.out.println("Node:"+b.getName()+" Dist:"+nextSurVProposedDist);
            distMap.put(b, nextSurVProposedDist);
        }
    }
}

Code Formatted by ToGoTutor

Output:
Node:Six Dist:9
Node:Four Dist:6
Node:One Dist:23
Node:Three Dist:11
Node:Two Dist:21
Complete
Node:Six Dist:9
Node:Four Dist:6
Node:One Dist:23
Node:Three Dist:11
Node:Two Dist:21
Complete