I am trying to find shortest pair of edge-disjoint paths between a given pair of vertices and I was following this algorithm which in general is Suurballe's algorithm I guess.
Here is the algorithm:
- Run the shortest path algorithm for the given pair of vertices (I am using Dijkstra algorithm)
- Replace each edge of the shortest path (equivalent to two oppositely directed arcs) by a single arc directed towards the source vertex
- Make the length of each of the above arcs negative
- Run the shortest path algorithm (Note: the algorithm should accept negative costs)
- Erase the overlapping edges of the two paths found, and reverse the direction of the remaining arcs on the first shortest path such that each arc on it is directed towards the sink vertex now. The desired pair of paths results.
In that wikipedia, first step is to find the shortest path between source and destination node which I am able to do it correctly as shown in the below code by using Dijkstra Algorithm -
public class DijkstraAlgorithm {
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("A", "G", 8),
new Graph.Edge("A", "B", 1),
new Graph.Edge("A", "E", 1),
new Graph.Edge("B", "C", 1),
new Graph.Edge("B", "E", 1),
new Graph.Edge("B", "F", 2),
new Graph.Edge("C", "G", 1),
new Graph.Edge("C", "D", 1),
new Graph.Edge("D", "F", 1),
new Graph.Edge("D", "Z", 1),
new Graph.Edge("E", "F", 4),
new Graph.Edge("F", "Z", 4),
new Graph.Edge("G", "Z", 2),
};
private static final String START = "A";
private static final String END = "Z";
public static void main(String[] args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
// print the shortest path using Dijkstra algorithm
g.printPath(END);
// g.printAllPaths();
}
}
class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
/** One edge of the graph (only used by Graph constructor) */
public static class Edge {
public final String v1, v2;
public final int dist;
public Edge(String v1, String v2, int dist) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
}
}
/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
public final String name;
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
public Vertex previous = null;
public final Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();
public Vertex(String name) {
this.name = name;
}
private void printPath() {
if (this == this.previous) {
System.out.printf("%s", this.name);
} else if (this.previous == null) {
System.out.printf("%s(unreached)", this.name);
} else {
this.previous.printPath();
System.out.printf(" -> %s(%d)", this.name, this.dist);
}
}
public int compareTo(Vertex other) {
if (dist==other.dist)
return name.compareTo(other.name);
return Integer.compare(dist, other.dist);
}
}
/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
graph = new HashMap<String, Vertex>(edges.length);
//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1))
graph.put(e.v1, new Vertex(e.v1));
if (!graph.containsKey(e.v2))
graph.put(e.v2, new Vertex(e.v2));
}
//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also for an undirected graph
}
}
/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
return;
}
final Vertex source = graph.get(startName);
NavigableSet<Vertex> q = new TreeSet<Vertex>();
// set-up vertices
for (Vertex v : graph.values()) {
v.previous = v == source ? source : null;
v.dist = v == source ? 0 : Integer.MAX_VALUE;
q.add(v);
}
dijkstra(q);
}
/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
Vertex u, v;
while (!q.isEmpty()) {
u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
if (u.dist == Integer.MAX_VALUE)
break; // we can ignore u (and any other remaining vertices) since they are unreachable
//look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); //the neighbour in this iteration
final int alternateDist = u.dist + a.getValue();
if (alternateDist < v.dist) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
}
}
}
}
/** Prints a path from the source to the specified vertex */
public void printPath(String endName) {
if (!graph.containsKey(endName)) {
System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
return;
}
graph.get(endName).printPath();
System.out.println();
}
/** Prints the path from the source to every vertex (output order is not guaranteed) */
public void printAllPaths() {
for (Vertex v : graph.values()) {
v.printPath();
System.out.println();
}
}
}
Now I am stuck in executing the remaining steps in that algorithm so that I can get shortest pair of edge-disjoint paths between a given pair of vertices.
The shortest path from node A to node Z is ABCDZ, while the shortest pair is ABCGZ and AEBFDZ.
