aboutsummaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
authorPacien TRAN-GIRARD2015-10-10 21:01:15 +0200
committerPacien TRAN-GIRARD2015-10-10 21:01:15 +0200
commitc585327bc8707783715ada45f71ddf4416d6c384 (patch)
tree1c4cf3c91d2f112fcf7e21bee40ddd03995e632d /src/main
parentaffd57392742e4d04139c1757bb79398a443eacf (diff)
downloadseam-stitcher-c585327bc8707783715ada45f71ddf4416d6c384.tar.gz
Implement shortest path finder
Diffstat (limited to 'src/main')
-rw-r--r--src/main/java/Seam.java55
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 @@
5public final class Seam { 5public final class Seam {
6 6
7 /** 7 /**
8 * Find the best predecessors between {@code from} and {@code to} using Dijkstra's algorithm
9 *
10 * @param successors adjacency list for all vertices
11 * @param costs weight for all vertices
12 * @param from first vertex
13 * @return best predecessor of each vertex
14 */
15 private static int[] findBestPredecessors(int[][] successors, float[] costs, int from) {
16 int nbVertices = successors.length;
17 float distances[] = new float[nbVertices];
18 int bestPredecessors[] = new int[nbVertices];
19
20 for (int v = 0; v < nbVertices; ++v) {
21 distances[v] = Float.POSITIVE_INFINITY;
22 bestPredecessors[v] = -1;
23 }
24
25 distances[from] = costs[from];
26 boolean modified = true;
27
28 while (modified) {
29 modified = false;
30 for (int v = 0; v < nbVertices; ++v)
31 for (int n : successors[v])
32 if (distances[n] > distances[v] + costs[n]) {
33 distances[n] = distances[v] + costs[n];
34 bestPredecessors[n] = v;
35 modified = true;
36 }
37 }
38
39 return bestPredecessors;
40 }
41
42 /**
8 * Compute shortest path between {@code from} and {@code to} 43 * Compute shortest path between {@code from} and {@code to}
9 * 44 *
10 * @param successors adjacency list for all vertices 45 * @param successors adjacency list for all vertices
@@ -14,8 +49,24 @@ public final class Seam {
14 * @return a sequence of vertices, or {@code null} if no path exists 49 * @return a sequence of vertices, or {@code null} if no path exists
15 */ 50 */
16 public static int[] path(int[][] successors, float[] costs, int from, int to) { 51 public static int[] path(int[][] successors, float[] costs, int from, int to) {
17 // TODO path 52 int[] bestPredecessors = Seam.findBestPredecessors(successors, costs, from);
18 return null; 53
54 int count = 0; // we could have used a Deque<Integer>, but we could not have returned an int[]; CC Pr. Odersky
55 int predecessor = -1, newPredecessor = to;
56 while (newPredecessor > -1) {
57 predecessor = newPredecessor;
58 newPredecessor = bestPredecessors[newPredecessor];
59 ++count;
60 }
61
62 if (predecessor != from) return null; // "no way!"
63
64 int[] path = new int[count];
65 path[count - 1] = to;
66 for (int v = count - 2; v >= 0; --v)
67 path[v] = bestPredecessors[path[v + 1]];
68
69 return path;
19 } 70 }
20 71
21 /** 72 /**