graph theory
Hi.
Does anyone of you know some nice (and possibly already implemented) algorithms for the k-shortest-path problem? In particular, I am interested in some special features: it has to work with a directed, weighted graph and should ignore loops, i.e. it should work with simple paths. And I don't want it to cut edges after finding a path.
Here is a small example with edges weighted 1 each, the direction is from left to right:
A - - - B - C
\/
F - G
So the algorithm should yield A-B-C as the shortest, and A-F-G-C as the second-shortest path.
I am glad for every hint, thank you in advanced,
greetings
Norman
Message was edited by:
Waldmeister_iii
Hi all.
First, thanks for yours answers and sorry for me not answering so long!
In my graph, I have a start and an end node, for which I want to have all or just k shortest paths. So in my example, the goal would bei to extract A-B-C and A-F-G-B-C as the two shortest paths available, if k is 2.
Here are some constraints on my graph:
- size: 10.000 to 1.000.000 nodes with 20-100 edges each
- the graph is propably non-connected
- I only want to search up to a certain depth, while the depth is definded by hops
- loops should be ignored
I have implemented a solution for near-shortest paths, using this paper: "Near-shortest and K-shortest simple paths" by Carlyle and Woods. The solution works, but not as fast as I would like it to. This is due to the following fact: I use Dijkstra all-pairs shortest-path algorithm first for calculatin the shortest paths for each node to each other node (within a graph of n nodes I have to run Dijkstra n times). This is quite fast. Now, for each shortest path from each node to each other node, I start the NSP (near-shortest-paths) calculations. So I have to run the NSP-algorithm n*(n-m) times, with m being the number of nodes not reachable by a shortest path at all. And this now chews up my computing power for a long long time... :)
So I hope I could make my problem a little bit more understandable, thanks again for your answers,
Greetings,
Norman
This is interesting. I thought about it a few days and came up with a variation of Dijsktra that supports not one shortest but k shortest paths. If you think of Dijkstra as generating a tree that spreads out from the root (startNode), we now simply allow k branches to overlap at a node.
Since it was just a quick test and Dijsktra is well known, I have not commented that thoroughly. If you have any questions just ask. :)
import java.util.*;
/*
* @author Thomas Horstmeyer
*/
public class KShortestPath {
private final DirectedGraph graph;
private final Object startNode, targetNode;
private final int k;
private final boolean pathsMustBeSimple;
private HashMap<Object, MultiPathInfo> pathsByNode;
public KShortestPath(DirectedGraph graph, Object startNode, Object targetNode, int k, boolean pathsMustBeSimple) {
this.graph = graph;
this.startNode = startNode;
this.targetNode = targetNode;
this.k = k;
this.pathsMustBeSimple = pathsMustBeSimple;
}
public void compute() {
pathsByNode = new HashMap<Object, MultiPathInfo>();
MultiPathInfo targetPathInfos = new MultiPathInfo();
pathsByNode.put(targetNode, targetPathInfos);
PriorityQueue<PathInfo> candidates = new PriorityQueue<PathInfo>();
candidates.offer(new PathInfo(startNode, 0d, null));
while(targetpathInfos.isIncomplete() && !candidates.isEmpty()) {
PathInfo pi = candidates.poll();
System.out.print("inspecting candidate at "+pi.endNode+" weight="+pi.weight);
MultiPathInfo mpi = pathsByNode.get(pi.endNode);
if (mpi == null) {
mpi = new MultiPathInfo();
pathsByNode.put(pi.endNode, mpi);
}
if (mpi.isIncomplete() && (!pathsMustBeSimple || isSimplePath(pi))) {
System.out.println(" ...taken");
mpi.addPathInfo(pi);
Iterator it = graph.getSuccNodes(pi.endNode).iterator();
while (it.hasNext()) {
Object node = it.next();
candidates.add(new PathInfo(node, pi.weight + graph.getEdgeWeight(pi.endNode, node), pi));
System.out.println("\tcreated candidate at "+node+" weight="+(pi.weight + graph.getEdgeWeight(pi.endNode, node))+")");
}
}
else System.out.println(" ...discarded");
}
}
// checks whether endNode appears more than once in the path
private boolean isSimplePath(PathInfo path) {
Object node = path.endNode;
while (path.lead != null) {
path = path.lead;
if (node.equals(path.endNode)) return false;
}
return true;
}
public void printPaths() {
MultiPathInfo mpi = pathsByNode.get(targetNode);
for (int i=0; i<mpi.paths.length; i++) {
PathInfo pi = mpi.paths[i];
StringBuilder sb = new StringBuilder();
while (pi != null) {
sb.insert(0, ", ");
sb.insert(0, pi.endNode);
pi = pi.lead;
}
sb.insert(0, " : ");
sb.insert(0, mpi.paths[i].weight);
System.out.println(sb.toString());
}
}
private static class PathInfo implements Comparable{
double weight;
Object endNode;
PathInfo lead;
public PathInfo(Object endNode, double weight, PathInfo lead) {
this.endNode = endNode;
this.weight = weight;
this.lead = lead;
}
//inconsistent with equals
public int compareTo(Object o) {
PathInfo pi = (PathInfo) o;
if (weight >< pi.weight) return -1;
if (weight > pi.weight) return 1;
return 0;
}
}
private class MultiPathInfo {
PathInfo[] paths = new PathInfo[k];
int nextFreePosition = 0;
void addPathInfo(PathInfo pi) {
if (nextFreePosition < k) paths[nextFreePosition++] = pi;
}
boolean isIncomplete() {
return nextFreePosition < k;
}
}
}
Let's take a look at the complexity:
Let graph have n nodes and m edges.
The algorithm creates at most m*k candidates. Storing and removing them in the PriorityQueue takes O(log (k*m)).
So we have a complexity of O(m*k*log(k*m)). We could improve this to O(m*k) using a Fibonacci heap.
For simple paths the additional check adds a factor of (length of path) which is bounded by n.
It is also possible to bound the search depth with an additional hop-distance field in PathInfo.
And I can see some space for improvement in the check for simpleness of a path - not necessarily complexity-wise.
If you try out this approach I would really be interested in how it competes with your current approach.
Greetings,
Thomas
