# Brute force shortest path in Java

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem.

Below is my version. It's super slow, but I find it funny.

BruteForceShortestPath.java:

package net.coderodde.graph.experimental;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
* This class implements a brute force shortest path algorithm for directed,
* weighted graphs.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Sep 25, 2015)
*/
public class BruteForceShortestPath {

private final DirectedGraphNode source;
private final DirectedGraphNode target;
private final DirectedGraphWeightFunction weightFunction;
private final Set<DirectedGraphNode> visitedSet = new HashSet<>();
private final Map<DirectedGraphNode, DirectedGraphNode> parentMap =
new HashMap<>();

public static List<DirectedGraphNode>
search(DirectedGraphNode source,
DirectedGraphNode target,
DirectedGraphWeightFunction weightFunction) {
Objects.requireNonNull(source, "The source node is null.");
Objects.requireNonNull(target, "The target node is null.");
Objects.requireNonNull(weightFunction, "The weight function is null.");

return new BruteForceShortestPath(source,
target,
weightFunction).search();
}

private BruteForceShortestPath(DirectedGraphNode source,
DirectedGraphNode target,
DirectedGraphWeightFunction weightFunction) {
this.source = source;
this.target = target;
this.weightFunction = weightFunction;
this.parentMap.put(source, null);
}

private double w(DirectedGraphNode tail, DirectedGraphNode head) {
}

private double search(DirectedGraphNode current,
double costFromSource,
double bestKnownCost) {
if (current.equals(target)) {
return costFromSource;
}

if (costFromSource >= bestKnownCost) {
return bestKnownCost;
}

double currentCost;

for (DirectedGraphNode child : current.children()) {
if (!visitedSet.contains(child)) {
currentCost = search(child,
costFromSource + w(current, child),
bestKnownCost);

if (bestKnownCost > currentCost) {
bestKnownCost = currentCost;
parentMap.put(child, current);
}
}
}

visitedSet.remove(current);
return bestKnownCost;
}

private List<DirectedGraphNode> search() {
search(source, 0.0, Double.POSITIVE_INFINITY);

if (!parentMap.containsKey(target)) {
return Collections.<DirectedGraphNode>emptyList();
}

return tracebackPath();
}

private List<DirectedGraphNode> tracebackPath() {
DirectedGraphNode current = target;
List<DirectedGraphNode> path = new ArrayList<>();

while (current != null) {
current = parentMap.get(current);
}

Collections.<DirectedGraphNode>reverse(path);
return path;
}
}


DirectedGraphNode.java (ignore):

package net.coderodde.graph.experimental;

import java.util.Collections;
import java.util.Objects;
import java.util.Set;

/**
* This class implements directed graph nodes.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Sep 25, 2015)
*/
public class DirectedGraphNode {

private final String name;
private final Set<DirectedGraphNode> children = new LinkedHashSet<>();

public DirectedGraphNode(String name) {
Objects.requireNonNull(name, "The name of a new node is null.");
this.name = name;
}

}

public Set<DirectedGraphNode> children() {
return Collections.<DirectedGraphNode>unmodifiableSet(children);
}

@Override
public String toString() {
return "[DirectedGraphNode \"" + name + "\"]";
}

@Override
public boolean equals(Object o) {
if (!(o instanceof DirectedGraphNode)) {
return false;
}

return name.equals(((DirectedGraphNode) o).name);
}

// Generated by NetBeans.
@Override
public int hashCode() {
int hash = 7;
hash = 17 * hash + Objects.hashCode(this.name);
return hash;
}
}


DirectedGraphWeightFunction.java (ignore):

package net.coderodde.graph.experimental;

import java.util.HashMap;
import java.util.Map;

/**
* This class implements directed graph weight functions.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class DirectedGraphWeightFunction {

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

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

}

public double get(DirectedGraphNode tail, DirectedGraphNode head) {
}
}


Demo.java (ignore):

import java.util.List;
import net.coderodde.graph.experimental.BruteForceShortestPath;
import net.coderodde.graph.experimental.DirectedGraphNode;
import net.coderodde.graph.experimental.DirectedGraphWeightFunction;

public class Demo {

public static void main(final String... args) {
DirectedGraphNode a = new DirectedGraphNode("A");
DirectedGraphNode b = new DirectedGraphNode("B");
DirectedGraphNode c = new DirectedGraphNode("C");
DirectedGraphNode d = new DirectedGraphNode("D");
DirectedGraphNode e = new DirectedGraphNode("E");
DirectedGraphNode f = new DirectedGraphNode("F");

DirectedGraphWeightFunction wf = new DirectedGraphWeightFunction();

/* The first graph:
*
* +--2.0--B--1.0--D--4.0--E
* |               |\
* A--3.5--C--3.0--+ +--1.6--F
*/

long ta = System.currentTimeMillis();
List<DirectedGraphNode> path = BruteForceShortestPath.search(a, f, wf);
long tb = System.currentTimeMillis();

System.out.println("Time: " + (tb - ta) + " ms.");
printPath(path);

System.out.println("\nLarger demo:");

// (1) Change 4 to 5, and "brute-forceness" will become obvious. :)
// (2) Change the cost arguments to their respective inverses
// (i.e., -1.0 & -1.414), and see what happens.
Data data = getLargerGraph(8, 1.0, 1.414);
DirectedGraphNode[][] G = data.gridGraph;
DirectedGraphWeightFunction wf2 = data.weightFunction;

// Top-left corner node [0, 0].
DirectedGraphNode source = G[0][0];

// [x = 3, y = 2].
DirectedGraphNode target = G[6][7];

System.out.println("Source: " + source);
System.out.println("Target: " + target);

ta = System.currentTimeMillis();
path = BruteForceShortestPath.search(source, target, wf2);
tb = System.currentTimeMillis();

System.out.println("Time: " + (tb - ta) + " ms.");
printPath(path);
}

private static final class Data {
DirectedGraphNode[][] gridGraph;
DirectedGraphWeightFunction weightFunction;
}

/**
* Generates a grid graph with width and height of {@code N} nodes.
*/
private static Data getLargerGraph(int N,
double horzVertCost,
double diagonalCost) {
DirectedGraphNode[][] graph = new DirectedGraphNode[N][N];
DirectedGraphWeightFunction f = new DirectedGraphWeightFunction();

for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
graph[y][x] = new DirectedGraphNode("[" + x + ", " + y + "]");
}
}

// Horizontal edges.
for (int x = 0; x < N - 1; x++) {
for (int y = 0; y < N; y++) {
f.put(graph[y][x], graph[y][x  + 1], horzVertCost);
f.put(graph[y][x + 1], graph[y][x], horzVertCost);
}
}

// Vertical edges.
for (int y = 0; y < N - 1; y++) {
for (int x = 0; x < N; x++) {
f.put(graph[y][x], graph[y + 1][x], horzVertCost);
f.put(graph[y + 1][x], graph[y][x], horzVertCost);
}
}

// Diagonal "\"-edges.
for (int x = 0; x < N - 1; x++) {
for (int y = 0; y < N - 1; y++) {
f.put(graph[y][x], graph[y + 1][x + 1], diagonalCost);
f.put(graph[y + 1][x + 1], graph[y][x], diagonalCost);
}
}

// Diagonal "/"-edges.
for (int x = 0; x < N - 1; x++) {
for (int y = 1; y < N; y++) {
f.put(graph[y][x], graph[y - 1][x + 1], diagonalCost);
f.put(graph[y - 1][x + 1], graph[y][x], diagonalCost);
}
}

Data ret = new Data();
ret.gridGraph = graph;
ret.weightFunction = f;
return ret;
}

private static void printPath(List<DirectedGraphNode> path) {
for (DirectedGraphNode node : path) {
System.out.println(node);
}
}
}


I posted all other classes required for running the demonstration, yet they are not of my top concern. So, anything I could do to improve the program text?