Implement shortest path finder

1 files changed, 53 insertions, 2 deletions

diff --git a/src/main/java/Seam.java b/src/main/java/Seam.java
index 1cb4a0c..d74dff7 100644
--- a/src/main/java/Seam.java
+++ b/src/main/java/Seam.java
@@ -5,6 +5,41 @@
 public final class Seam {
 
     /**
+     * Find the best predecessors between {@code from} and {@code to} using Dijkstra's algorithm
+     *
+     * @param successors adjacency list for all vertices
+     * @param costs      weight for all vertices
+     * @param from       first vertex
+     * @return best predecessor of each vertex
+     */
+    private static int[] findBestPredecessors(int[][] successors, float[] costs, int from) {
+        int nbVertices = successors.length;
+        float distances[] = new float[nbVertices];
+        int bestPredecessors[] = new int[nbVertices];
+
+        for (int v = 0; v < nbVertices; ++v) {
+            distances[v] = Float.POSITIVE_INFINITY;
+            bestPredecessors[v] = -1;
+        }
+
+        distances[from] = costs[from];
+        boolean modified = true;
+
+        while (modified) {
+            modified = false;
+            for (int v = 0; v < nbVertices; ++v)
+                for (int n : successors[v])
+                    if (distances[n] > distances[v] + costs[n]) {
+                        distances[n] = distances[v] + costs[n];
+                        bestPredecessors[n] = v;
+                        modified = true;
+                    }
+        }
+
+        return bestPredecessors;
+    }
+
+    /**
      * Compute shortest path between {@code from} and {@code to}
      *
      * @param successors adjacency list for all vertices
@@ -14,8 +49,24 @@ public final class Seam {
      * @return a sequence of vertices, or {@code null} if no path exists
      */
     public static int[] path(int[][] successors, float[] costs, int from, int to) {
-        // TODO path
-        return null;
+        int[] bestPredecessors = Seam.findBestPredecessors(successors, costs, from);
+
+        int count = 0; // we could have used a Deque<Integer>, but we could not have returned an int[]; CC Pr. Odersky
+        int predecessor = -1, newPredecessor = to;
+        while (newPredecessor > -1) {
+            predecessor = newPredecessor;
+            newPredecessor = bestPredecessors[newPredecessor];
+            ++count;
+        }
+
+        if (predecessor != from) return null; // "no way!"
+
+        int[] path = new int[count];
+        path[count - 1] = to;
+        for (int v = count - 2; v >= 0; --v)
+            path[v] = bestPredecessors[path[v + 1]];
+
+        return path;
     }
 
     /**