Dijkstra’s Single Source Shortest Path Algorithm in Java and DFS/BFS

I find that there are not a lot of good examples of this with heaps so here is my implementation as a coding example (in java).

First let me define the underlying Vertex/Edge data structure with the following classes:

public class Edge{
    public double weight;
    public Vertex destination;

    public Edge(Vertex destination, double weight) {
        this.destination = destination;
        this.weight = weight;
    }
}

public class Vertex implements Comparable<Vertex>{

    public String name;
    public ArrayList<Edge> adjacentEdges; //list of outgoing edges
    public Double minDistance = Double.POSITIVE_INFINITY; //used for SSP

    public Vertex(String name) {
        this.name = name;
        this.adjacentEdges = new ArrayList<Edge>();
    }

    public void addEdge(Vertex dest, double cost){
        adjacentEdges.add(new Edge(dest, cost));
    }

    @Override
    public int compareTo(Vertex o) {
        return (int)(minDistance - o.minDistance); //to be used for heaps
    }
}

The graph class creates an adjacency list for nodes provided and a hashmap to prevent node duplication.

public class Graph {

    public ArrayList<Vertex> adjacenyList;
    HashMap<String, Vertex> vertexMap;

    public Graph() {
        this.adjacenyList = new ArrayList<Vertex>();
        vertexMap = new HashMap<String, Vertex>();
    }

    public void addNodes(String vertex, String destination, double distance){
        //check if vertex already exists
        Vertex src = getNodeOrCreate(vertex);
        Vertex dest = getNodeOrCreate(destination);
        //add edge to vertex
        src.addEdge(dest, distance);
    }

    private Vertex getNodeOrCreate(String node){
        Vertex v;
        if(vertexMap.containsKey(node)){
            v = vertexMap.get(node);
        }else{
            v = new Vertex(node);
            vertexMap.put(node, v);
            adjacenyList.add(v);
        }
        return v;
    }

    public Vertex getVertexByName(String name){
        return vertexMap.get(name);
    }

    public void printAdjacencyList(){
        for(Vertex v : adjacenyList){
            System.out.print("Vertex: " + v.name);
            for(Edge e : v.adjacentEdges){
                System.out.print(" " + e.destination.name + "/" + e.weight);
            }
            System.out.println();
        }
    }

    //algorithms

    public ArrayList<Vertex> depthFirstSearch(Vertex start) {
        Vertex head = start;
        Stack<Vertex> stack = new Stack<Vertex>();
        ArrayList<Vertex> result = new ArrayList<Vertex>(); //visited
        stack.push(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            if (!result.contains(head)) {
                result.add(head);
                for (Edge e : head.adjacentEdges) {
                    stack.push(e.destination);
                }
            }
        }
        return result;
    }

    public ArrayList<Vertex> breadthFirstSearch(Vertex start){
        Queue<Vertex> queue = new LinkedList<Vertex>();
        ArrayList<Vertex> result = new ArrayList<Vertex>(); //visited
        Vertex head = start;
        queue.add(head);
        result.add(head);
        while(!queue.isEmpty()){
            head = queue.poll();
            for (Edge e : head.adjacentEdges){
                if(!result.contains(e.destination)){
                    queue.add(e.destination);
                    result.add(e.destination);
                }
            }
        }
        return result;
    }

    public Double djksraShortestPath(Vertex src, Vertex dest){
        //reset mins
        resetMins();
        PriorityQueue<Vertex> heap = new PriorityQueue<Vertex>();
        //init all edges as infinity
        src.minDistance = 0.0;
        for(Vertex v : adjacenyList){
            heap.add(v);
        }

        Vertex next;
        while(!heap.isEmpty()){
            next = heap.poll(); //extract min
            for(Edge e : next.adjacentEdges){
                Double cost = next.minDistance + e.weight;
                if(cost < e.destination.minDistance){
                    e.destination.minDistance = cost;
                }
            }
        }
        return dest.minDistance;
    }
    public Double djksraShortestPath(String src, String dest){

        return djksraShortestPath(getVertexByName(src), getVertexByName(dest));
    }

    private void resetMins(){
        for(Vertex v : adjacenyList){
            v.minDistance = Double.POSITIVE_INFINITY;
        }
    }
}

Its always important to use test frameworks to test code, but since this is a simple console application I do all the verification in main.

    public static void complicatedGraph(){
        //complicated graph
        Graph weightedGraph = new Graph();
        weightedGraph.addNodes("A","B", 20);
        weightedGraph.addNodes("A","D", 80);
        weightedGraph.addNodes("A","G", 90);
        weightedGraph.addNodes("B","F", 10);
        weightedGraph.addNodes("E","B", 50);
        weightedGraph.addNodes("E","G", 30);
        weightedGraph.addNodes("G","A", 20);
        weightedGraph.addNodes("D","G", 20);
        weightedGraph.addNodes("D","C", 10);
        weightedGraph.addNodes("F","D", 40);
        weightedGraph.addNodes("F","C", 10);
        weightedGraph.addNodes("C","F", 50);
        weightedGraph.addNodes("C","D", 10);
        weightedGraph.addNodes("C","H", 20);
        weightedGraph.printAdjacencyList();

        ArrayList<Vertex> bfs = weightedGraph.breadthFirstSearch(weightedGraph.getVertexByName("A"));
        ArrayList<Vertex> dfs = weightedGraph.depthFirstSearch(weightedGraph.getVertexByName("A"));
        System.out.print("BFS ");
        printVertexList(bfs);
        System.out.print("DFS ");
        printVertexList(dfs);
        
        System.out.println("");
        System.out.println("Shortest distance between A and H is " + weightedGraph.djksraShortestPath("A", "H"));
        System.out.println("Shortest distance between A and E is " + weightedGraph.djksraShortestPath("A", "E"));
        System.out.println("Shortest distance between D and H is " + weightedGraph.djksraShortestPath("D", "H"));

    }

    public static void simpleGraph(){
        Graph graph = new Graph();
        graph.addNodes("A","B", 1);
        graph.addNodes("A","D", 1);
        graph.addNodes("A","G", 1);
        graph.addNodes("B","E", 1);
        graph.addNodes("B","F", 1);
        graph.addNodes("E","B", 1);
        graph.addNodes("E","G", 1);
        graph.addNodes("G","E", 1);
        graph.addNodes("G","A", 1);
        graph.addNodes("D","A", 1);
        graph.addNodes("D","F", 1);
        graph.addNodes("F","B", 1);
        graph.addNodes("F","C", 1);
        graph.addNodes("C","F", 1);
        graph.addNodes("C","H", 1);
        graph.addNodes("H","C", 1);
        graph.printAdjacencyList();
        ArrayList<Vertex> bfs = graph.breadthFirstSearch(graph.getVertexByName("A"));
        ArrayList<Vertex> dfs = graph.depthFirstSearch(graph.getVertexByName("A"));
        System.out.print("BFS ");
        printVertexList(bfs);
        System.out.print("DFS ");
        printVertexList(dfs);

        System.out.println("Shortest distance between A and H is " + graph.djksraShortestPath("A", "H"));
    }

    public static void main(String [ ] args){
        simpleGraph();
        complicatedGraph();
    }

The output:

Simple Graph
Vertex: A B/1.0 D/1.0 G/1.0
Vertex: B E/1.0 F/1.0
Vertex: D A/1.0 F/1.0
Vertex: G E/1.0 A/1.0
Vertex: E B/1.0 G/1.0
Vertex: F B/1.0 C/1.0
Vertex: C F/1.0 H/1.0
Vertex: H C/1.0
BFS A B D G E F C H
DFS A G E B F C H D
Shortest distance between A and H is 4.0
Complicated Graph
Vertex: A B/20.0 D/80.0 G/90.0
Vertex: B F/10.0
Vertex: D G/20.0 C/10.0
Vertex: G A/20.0
Vertex: F D/40.0 C/10.0
Vertex: E B/50.0 G/30.0
Vertex: C F/50.0 D/10.0 H/20.0
Vertex: H
BFS A B D G F C H
DFS A G D C H F B
Shortest distance between A and H is 60.0
Shortest distance between A and E is Infinity
Shortest distance between D and H is 30.0

Word Prediction App Part 2: Adding Some O(nlogn) Searching to the List Filter.

The previous list filter utilized brute force in effort to focus on figuring out how Apple designed its MVC structure. Part 2 of the code only changes the model.

Here is the header:

@property (nonatomic, readwrite, strong) NSArray *tableData;
@property (nonatomic, readwrite, strong) NSArray *filteredList;

- (NSArray *)sortWithSquence:(NSString *)sequence;
- (NSArray *)getSubArray:(NSArray *)array bySeq:(NSString *)charSeq;
- (NSInteger) binarySearchForMutableStringArray:(NSArray *)array bySeq:(NSString *)charSeq findLast:(BOOL)last;

I made the arrays normal NSArrays as NSMutableArrays should only really be used if the model data is going to be changed. Since the idea is just to create smaller subarrays, NSArrays are more suitable.

Here is the main code now:

#import "ListModel.h"

@implementation ListModel

@synthesize tableData = _tableData;
@synthesize filteredList = _filteredList;

- (id) init
{
    if(self == [super init])
    {
        NSLog(@"Creating table data");
        
        // Path to the plist (in the application bundle)
        NSString *path = [[NSBundle mainBundle] pathForResource:
                          @"words" ofType:@"plist"];
        
        // Build the array from the plist
        _tableData  = [[NSArray alloc] initWithContentsOfFile:path];
        
        NSLog(@"Created %ld rows", _tableData.count);
    }
    return self;
}


- (NSArray *)sortWithSquence:(NSString *)sequence
{
    if([sequence isEqualToString:@""]) //if no filter, return the regular list
    {
        return _tableData;
    }
    return [self getSubArray:_tableData bySeq:sequence];
}

- (NSArray *)getSubArray:(NSArray *)array bySeq:(NSString *)charSeq
{
    NSInteger first = [self binarySearchForMutableStringArray:array bySeq:charSeq findLast:NO];
    NSInteger last = [self binarySearchForMutableStringArray:array bySeq:charSeq findLast:YES];
    if(last-first >= 0 && (last != -1 || first != -1))
    {
        NSLog(@"Range (%ld, %ld)", first, last);
        return [array subarrayWithRange:NSMakeRange(first, last-first+1)];
    }
    else
    {
        NSLog(@"No matches found");
        return nil;
    }
}

//binary search implemented with character sequences
- (NSInteger) binarySearchForMutableStringArray:(NSArray *)array bySeq:(NSString *)charSeq findLast:(BOOL)last
{
    NSInteger low = 0;
    NSInteger high = [array count];
    NSInteger result = -1;
    while(low <= high)
    {
        NSInteger mid = (low + high)/2;
        NSString *midObj = [array objectAtIndex:mid]; // get middle
        NSComparisonResult compare = [midObj compare:charSeq options:NSCaseInsensitiveSearch range:NSMakeRange(0, charSeq.length)];
        if(compare == NSOrderedAscending)
        {
            low = mid + 1;
        }
        else if(compare == NSOrderedDescending)
        {
            high = mid - 1;
        }
        else
        {
            result = mid; // key found
            if(last)
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
    }
    return result; //no occurance
}


@end

To move away from the ugly brute force method, I utilized the binary search algorithm. The idea is to find the first occurrence of a character sequence, find the last, determine the range and give back a new spliced array pointer. Using ranges, we can use various points to just point to different sections of the array. This takes away the need to create any new arrays.

In part 3, I will optimize the list by storing the filtered values as the character sequence increases. For example

“A” will provide a list of all words that start with “A”. When the user types “AP”, I will have the algorithm index the previously spliced list to increase the speed at which it finds the next character sequence. If the user hits backspace, the previous list can be provided if available in memory, if not then the algorithm will have to re-index the main list. This will optimize performance and speed as the user gets closer and closer to the word they wish to type.

Part 4 will then look into using Core Data to better store the pre-processed data and finally part 5 will use the list filter logic to create a fast word predictor.