Comparing Dijkstra's SSSP algorithm against Bellman-Ford in Java

Question

Single source shortest path

In SSSP, we choose a node \$s\$ and we compute all the shortest path starting from \$s\$ towards all other nodes, thus computing a shortest path tree. Two most classical algorithms for doing that is Dijkstra's algorithm and Bellman-Ford algorithm.

Code

Below is my small Java library for comparing the two:

AbstractSingleSourceShortestPathAlgorithm.java

package net.coderodde.graph.sssp;

import java.util.Map;

/**
 * This interface defines the API for single-source shortest path algorithms.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 * @param <Node> the graph node type.
 */
public abstract class AbstractSingleSourceShortestPathAlgorithm<Node> {

    /**
     * Computes a shortest path tree starting from {@code sourceNode}, using 
     * {@code nodeExpander} as the child node generator, and 
     * {@code weightFunction} as the weight function.
     * 
     * @param sourceNode     the source node.
     * @param graph          the list of graph nodes.
     * @param nodeExpander   the node expander.
     * @param weightFunction the weight function of the graph.
     * @return a shortest path tree of the reachable graph.
     */
    public abstract ShortestPathTree<Node> 
        computeShortestPaths(Node sourceNode,
                             Graph<Node> graph,
                             ForwardNodeExpander<Node> nodeExpander,
                             DoubleWeightFunction<Node> weightFunction);

    protected ShortestPathTree<Node> 
        constructShortestPathTree(Map<Node, Node> parents,
                                  Map<Node, Double> distances,
                                  Node sourceNode,
                                  DoubleWeightFunction<Node> weightFunction) {
        return new ShortestPathTree<>(parents,
                                      distances,
                                      sourceNode,
                                      weightFunction);
    }
}

DoubleWeightFunction.java

package net.coderodde.graph.sssp;

/**
 * This interface defines the API for weight functions with weights of type 
 * {@code double}.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 * @param <Node> the graph node type.
 */
public interface DoubleWeightFunction<Node> {

    /**
     * Sets the weight of a directed arc {@code (from, to)}.
     * 
     * @param from   the tail node of the arc.
     * @param to     the head node of the arc.
     * @param weight the weight of the arc.
     */
    public void put(Node from, Node to, double weight);

    /**
     * Returns the weight of the directed arc {@code (from, to)}.
     * 
     * @param from the tail node of the arc.
     * @param to   the head node of the arc.
     * @return     the weight of the directed arc.
     */
    public double get(Node from, Node to);
}

ForwardNodeExpander.java

package net.coderodde.graph.sssp;

import java.util.List;

/**
 * This interface defines the API for expanding a graph node in forward
 * direction (from a node to its children).
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 * @param <Node> the graph node type.
 */
public interface ForwardNodeExpander<Node> {

    /**
     * Generates and returns a list of child nodes of {@code node}.
     * 
     * @param node the node to expand.
     * @return the list of child nodes.
     */
    public List<Node> expand(Node node);
}

Graph.java

package net.coderodde.graph.sssp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements a graph.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 28, 2017)
 * @param <Node> the graph node type.
 */
public final class Graph<Node> implements Iterable<Node> {

    private final Set<Node> nodeSet = new HashSet<>();

    public void addNode(Node node) {
        nodeSet.add(Objects.requireNonNull(node, "The input node is null."));
    }

    public int size() {
        return nodeSet.size();
    }

    public List<Node> getNodeList() {
        return new ArrayList<>(nodeSet);
    }

    @Override
    public Iterator<Node> iterator() {
        return Collections.unmodifiableSet(nodeSet).iterator();
    }
}

GraphPath.java

package net.coderodde.graph.sssp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * This class implements a graph path.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 28, 2017)
 * @param <Node> the graph node type.
 */
public final class GraphPath<Node> implements Iterable<Node> {

    private final List<Node> path;
    private final double cost;

    GraphPath(List<Node> pathAsList, 
              DoubleWeightFunction<Node> weightFunction) {
        this.path = new ArrayList<>(pathAsList);

        double cost = 0.0;

        for (int i = 0; i < path.size() - 1; ++i) {
            cost += weightFunction.get(path.get(i), path.get(i + 1));
        }

        this.cost = cost;
    }

    public int size() {
        return path.size();
    }

    public Node getNode(int index) {
        return path.get(index);
    }

    public double getCost() {
        return cost;
    }

    @Override
    public Iterator<Node> iterator() {
        return Collections.unmodifiableList(path).iterator();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        String separator = "";

        for (Node node : path) {
            sb.append(separator);
            separator = " -> ";
            sb.append(node.toString());
        }

        return sb.append(", cost: ")
                 .append(cost)
                 .append("]")
                 .toString();
    }
}

ShortestPathTree.java

package net.coderodde.graph.sssp;

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

/**
 * This class stores a shortest path tree returned by a single-source shortest
 * path algorithm.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 * @param <Node> the graph node type.
 */
public final class ShortestPathTree<Node> {

    private final Map<Node, Node> parentMap;
    private final Map<Node, Double> distanceMap;
    private final Node sourceNode;
    private final DoubleWeightFunction<Node> weightFunction;

    ShortestPathTree(Map<Node, Node> parentMap,
                            Map<Node, Double> distanceMap,
                            Node sourceNode,
                            DoubleWeightFunction<Node> weightFunction) {
        this.parentMap = parentMap;
        this.distanceMap = distanceMap;
        this.sourceNode = sourceNode;
        this.weightFunction = weightFunction;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        } else if (o == null) {
            return false;
        } else if (!getClass().equals(o.getClass())) {
            return false;
        }

        ShortestPathTree<Node> other = (ShortestPathTree<Node>) o;
        return parentMap.equals(other.parentMap) && 
               distanceMap.equals(other.distanceMap);
    }

    public Node getSourceNode() {
        return sourceNode;
    }

    public GraphPath<Node> getPath(Node targetNode) {
        if (!parentMap.containsKey(targetNode)) {
            throw new IllegalStateException(
                    "Target node \"" + targetNode + "\" is not reachable " + 
                    "from \"" + sourceNode + "\".");
        }

        Node currentNode = targetNode;
        List<Node> path = new ArrayList<>();

        while (currentNode != null) {
            path.add(currentNode);
            currentNode = parentMap.get(currentNode);
        }

        Collections.reverse(path);
        return new GraphPath<>(path, weightFunction);
    }
}

BellmanFordSingleSourceShortestPathAlgorithm.java

package net.coderodde.graph.sssp.support;

import java.util.HashMap;
import java.util.Map;
import net.coderodde.graph.sssp.DoubleWeightFunction;
import net.coderodde.graph.sssp.ForwardNodeExpander;
import net.coderodde.graph.sssp.ShortestPathTree;
import net.coderodde.graph.sssp.AbstractSingleSourceShortestPathAlgorithm;
import net.coderodde.graph.sssp.Graph;

/**
 * This class implements Bellman-Ford algorithm for finding a shortest path tree
 * starting from a given node.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 * @param <Node> the graph node type.
 */
public class BellmanFordSingleSourceShortestPathAlgorithm<Node> 
        extends AbstractSingleSourceShortestPathAlgorithm<Node> {

    /**
     * Finds the shortest path tree starting from {@code sourceNode} using
     * Bellman-Ford algorithm.
     * 
     * @param sourceNode     the source node.
     * @param graph          the list of graph nodes.
     * @param nodeExpander   the node expander.
     * @param weightFunction the weight function.
     * @return the shortest path tree.
     */
    @Override
    public ShortestPathTree<Node> 
        computeShortestPaths(
                Node sourceNode,
                Graph<Node> graph,
                ForwardNodeExpander<Node> nodeExpander, 
                DoubleWeightFunction<Node> weightFunction) {
        Map<Node, Double> distances = new HashMap<>(graph.size());
        Map<Node, Node> parents = new HashMap<>(graph.size());

        distances.put(sourceNode, 0.0);
        parents.put(sourceNode, null);

        for (int i = 0; i < graph.size() - 1; ++i) {
            for (Node currentNode : graph) {
                for (Node childNode : nodeExpander.expand(currentNode)) {
                    double currentNodeDistance = 
                            distances.getOrDefault(currentNode,
                                                   Double.POSITIVE_INFINITY);

                    double childNodeDistance =
                            distances.getOrDefault(childNode,
                                                   Double.POSITIVE_INFINITY);

                    double weight = weightFunction.get(currentNode, childNode);

                    if (currentNodeDistance + weight < childNodeDistance) {
                        distances.put(childNode, 
                                      currentNodeDistance + weight);

                        parents.put(childNode, currentNode);
                    }
                }
            }
        }

        return constructShortestPathTree(parents, 
                                         distances, 
                                         sourceNode,
                                         weightFunction);
    }
}

DijkstraSingleSourceShortestPathAlgorithm.java

package net.coderodde.graph.sssp.support;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import net.coderodde.graph.sssp.DoubleWeightFunction;
import net.coderodde.graph.sssp.ForwardNodeExpander;
import net.coderodde.graph.sssp.ShortestPathTree;
import net.coderodde.graph.sssp.AbstractSingleSourceShortestPathAlgorithm;
import net.coderodde.graph.sssp.Graph;

/**
 * This class implements Dijkstra's algorithm for finding a shortest path tree
 * starting from a given node.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 * @param <Node> the graph node type.
 */
public class DijkstraSingleSourceShortestPathAlgorithm<Node>
extends AbstractSingleSourceShortestPathAlgorithm<Node>{

    /**
     * Finds the shortest path tree starting from {@code sourceNode} using
     * Dijkstra's algorithm.
     * 
     * @param sourceNode     the source node.
     * @param graph          ignored.
     * @param nodeExpander   the node expander.
     * @param weightFunction the weight function.
     * @return the shortest path tree.
     */
    @Override
    public ShortestPathTree<Node> 
        computeShortestPaths(Node sourceNode, 
                             Graph<Node> graph,
                             ForwardNodeExpander<Node> nodeExpander, 
                             DoubleWeightFunction<Node> weightFunction) {
        Map<Node, Double> distances = new HashMap<>(graph.size());
        Map<Node, Node> parents = new HashMap<>(graph.size());
        Set<Node> closed = new HashSet<>(graph.size());
        Queue<NodeHolder<Node>> open = new PriorityQueue<>(graph.size());

        distances.put(sourceNode, 0.0);
        parents.put(sourceNode, null);
        open.add(new NodeHolder<>(sourceNode, 0.0));

        while (!open.isEmpty()) {
            Node currentNode = open.remove().getNode();

            if (closed.contains(currentNode)) {
                continue;
            }

            closed.add(currentNode);

            for (Node childNode : nodeExpander.expand(currentNode)) {
                if (closed.contains(childNode)) {
                    continue;
                }

                double tentativeDistance = 
                        distances.get(currentNode) +
                        weightFunction.get(currentNode, childNode);

                if (!distances.containsKey(childNode) ||
                    distances.get(childNode) > tentativeDistance) {
                    distances.put(childNode, tentativeDistance);
                    parents.put(childNode, currentNode);
                    open.add(new NodeHolder<>(childNode, tentativeDistance));
                }
            }
        }

        return constructShortestPathTree(parents, 
                                         distances, 
                                         sourceNode, 
                                         weightFunction);
    }

    private static final class NodeHolder<Node> implements Comparable<NodeHolder<Node>> {

        private final double distance;
        private final Node node;

        NodeHolder(Node node, double distance) {
            this.distance = distance;
            this.node = node;
        }

        @Override
        public int compareTo(NodeHolder<Node> o) {
            return Double.compare(distance, o.distance);
        }

        Node getNode() {
            return node;
        }
    }
}

DirectedGraphNode.java

package net.coderodde.graph.sssp.support;

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

/**
 * This class implements a graph node in a directed graph.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 */
public final class DirectedGraphNode {

    private final int id;
    private final List<DirectedGraphNode> children = new ArrayList<>();

    public DirectedGraphNode(int id) {
        this.id = id;
    }

    public void addChild(DirectedGraphNode child) {
        children.add(child);
    }

    public List<DirectedGraphNode> getChildren() {
        return Collections.unmodifiableList(children);
    }

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        } else if (o == null) {
            return false;
        } else if (!getClass().equals(o.getClass())) {
            return false;
        }

        DirectedGraphNode other = (DirectedGraphNode) o;
        return id == other.id;
    }

    @Override
    public String toString() {
        return String.valueOf(id);
    }
}

DirectedGraphNodeForwardExpander.java

package net.coderodde.graph.sssp.support;

import java.util.List;
import net.coderodde.graph.sssp.ForwardNodeExpander;

/**
 * This class implements a forward node expander in directed graphs.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 */
public final class DirectedGraphNodeForwardExpander 
        implements ForwardNodeExpander<DirectedGraphNode> {

    @Override
    public List<DirectedGraphNode> expand(DirectedGraphNode node) {
        return node.getChildren();
    }
}

DirectedGraphWeightFunction.java

package net.coderodde.graph.sssp.support;

import java.util.HashMap;
import java.util.Map;
import net.coderodde.graph.sssp.DoubleWeightFunction;

/**
 * This class implements a weight function over a directed graph.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 27, 2017)
 */
public class DirectedGraphWeightFunction 
        implements DoubleWeightFunction<DirectedGraphNode> {

    private final Map<DirectedGraphNode,
                      Map<DirectedGraphNode, Double>> map = new HashMap<>();

    @Override
    public void put(DirectedGraphNode from, DirectedGraphNode to, double weight) {
        if (!map.containsKey(from)) {
            map.put(from, new HashMap<>());
        }

        map.get(from).put(to, weight);
    }

    @Override
    public double get(DirectedGraphNode from, DirectedGraphNode to) {
        return map.get(from).get(to);
    }
}

(The entire benchmark and unit tests are here.)

Output

=== Warming up...
=== Warming up done!

bechmark(), seed = 1509203446023
Dijkstra's algorithm in 0 milliseconds.
Bellman-Ford algorithm in 3490 milliseconds.
Algorithms agreed.

Unfortunately, Bellman-Ford seems to be inferior on random, sparse graphs.

Critique request

Please tell me anything that comes to mind. My primary concern is the API structure of the library.

Answer 1

The very first thing that stood out to me is the naming of your generics. Using Node as the name of the generic is very odd in the Java world. I would strongly suggest you rename the generic to a single letter. Java loves T for Type in cases for single generics or just the first letter of the concept it is trying to model. For example, in the Java source, the generics for map are:

Map<K,V>

Not

Map<Key,Value>

This might seem like such a big deal but from experience it can lead to really stupid bugs and unintended behavior that is a pain to track down. A simple example. Say we have an interface like so:

public interface Foo {
    public void fizz();
}

And two classes:

public class Bar implements Foo {
    public void fizz(){
        System.out.println("Bar");
    }
}
public class Baz implements Foo {
    public void fizz(){
        System.out.println("Baz");
    }
}

And finally you have a class like this:

public class FooBarBaz<Bar extends Foo> {
    private Bar bar;

    public FooBarBaz(Bar bar){
        this.bar = bar;
    }

    public void callFizzOnBar(){
        this.bar.fizz();
    }

    public void main(String[] args){
        Baz baz = new Baz();
        FooBarBaz<Baz> fbb = new FooBarBaz<>(baz);
        fbb.callFizzOnBar();
    }
}

See how that can lead to issues? I am not saying your codes does this this this badly right now. But just writing code when even has the ability to go down this hole should be avoided.

Answer 2

That's fast for Djikstra, I will just suppose that either the test graph is not large enough or there is a bug in timing it.

Bellman-Ford is O(|V||E|), code from wikipedia

function BellmanFord(list vertices, list edges, vertex source)
   ::distance[],predecessor[]

   // This implementation takes in a graph, represented as
   // lists of vertices and edges, and fills two arrays
   // (distance and predecessor) with shortest-path
   // (less cost/distance/metric) information

   // Step 1: initialize graph
   for each vertex v in vertices:
       distance[v] := inf             // At the beginning , all vertices have a weight of infinity
       predecessor[v] := null         // And a null predecessor

   distance[source] := 0              // Except for the Source, where the Weight is zero 

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"
   return distance[], predecessor[]

Instead of doing step 1 the code has

double currentNodeDistance = distances.getOrDefault(currentNode, Double.POSITIVE_INFINITY);

This makes an potential O(N) cost lookup (hash map worst case), and a potentially costly hashing and testing.

It would be better to has a fixed array that is pre-filled with Double.POSITIVE_INFINITY, saving the hashing, the collision detection (and the defaulting if that costs extra). This requires that the node has an identity numbered 1..|V|, which I think you already have in

private final int id;

Same with parent, change it to a directly index array.

The code has 3 loops

for (int i = 0; i < graph.size() - 1; ++i) {
    for (Node currentNode : graph) {
        for (Node childNode : nodeExpander.expand(currentNode)) {

This makes the algorithm O(N^3) if I understand your code correctly as all nodes could be connected to all, comparing with the wikipedia code it runs through the nodes an extra time.

The correct should be

for (Node currentNode : graph) {
    for (Node childNode : nodeExpander.expand(currentNode)) {

as the outer loop just repeat everything.

Assuming there is no negative values for the edges via your weightFunction. we can skip the third step.

Finally we would need to transform the resulting parent and distance to whatever you need which should hopefully not add to the Big-O time. Best would be to drop the two maps and used directly indexed arrays instead.