# Faster k-shortest path algorithm in Java

In the $$\k\$$-shortest path problem, we are searching for (at most) $$\k\$$ distinct, shortest paths connecting two given terminal nodes. You can see the previous version here. This implementation, however, represents the intermediate paths in the open list as linked lists so that extending such a path by one node runs in $$\\Theta(1)\$$ time. My code is below:

net.coderodde.graph.kshortest.impl.FasterDefaultShortestPathFinder

package net.coderodde.graph.kshortest.impl;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import net.coderodde.graph.DirectedGraphNode;
import net.coderodde.graph.DirectedGraphWeightFunction;
import net.coderodde.graph.kshortest.AbstractKShortestPathFinder;
import net.coderodde.graph.kshortest.Path;

/**
* This class implements a rather simple k-shortest path algorithm from
* <a href="https://en.wikipedia.org/wiki/K_shortest_path_routing#Algorithm">
* Wikipedia
* </a>. This version improves
* using linked lists of nodes as the paths.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jun 4, 2019)
*/
public class FasterDefaultKShortestPathFinder
extends AbstractKShortestPathFinder {

@Override
public List<Path>
findShortestPaths(DirectedGraphNode source,
DirectedGraphNode target,
DirectedGraphWeightFunction weightFunction,
int k) {
Objects.requireNonNull(source, "The source node is null.");
Objects.requireNonNull(target, "The target node is null.");
Objects.requireNonNull(weightFunction,
"The weight function is null.");
checkK(k);

Map<DirectedGraphNode, Integer> countMap = new HashMap<>();

while (!HEAP.isEmpty() && countMap.getOrDefault(target, 0) < k) {
DirectedGraphNode endNode = currentPath.getTailNode();
countMap.put(endNode, countMap.getOrDefault(endNode, 0) + 1);

if (endNode.equals(target)) {
}

if (countMap.get(endNode) <= k) {
for (DirectedGraphNode child : endNode.children()) {
}
}
}

}

private static final List<Path>

}

return paths;
}
}


net.coderodde.graph.kshortest.impl.LinkedPathNode

package net.coderodde.graph.kshortest.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import net.coderodde.graph.DirectedGraphWeightFunction;
import java.util.Objects;
import net.coderodde.graph.DirectedGraphNode;
import net.coderodde.graph.kshortest.Path;

/**
* This class represents a path in a graph. The only difference between
* {@link net.coderodde.graph.kshortest.Path} is that this class implements the
* path as a linked list of graph nodes. This arrangement allows us to extend
* any given path by one graph node in constant time.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Jun 4, 2019)
*/

private final DirectedGraphWeightFunction weightFunction;
private final DirectedGraphNode node;
private double totalCost;

DirectedGraphNode node) {
this.weightFunction =
Objects.requireNonNull(
weightFunction,
"The input weight function is null.");

this.node = Objects.requireNonNull(node, "The input node is null.");
this.totalCost = 0.0;
}

this.weightFunction = path.weightFunction;
this.node = node;
}

}

}

DirectedGraphNode getTailNode() {
return this.node;
}

Path toPath() {
List<DirectedGraphNode> path = new ArrayList<>();

while (node != null) {
}

Collections.<DirectedGraphNode>reverse(path);
return new Path(path, this.weightFunction);
}

@Override