diff options
Diffstat (limited to 'src/main')
-rw-r--r-- | src/main/java/Seam.java | 55 |
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 @@ | |||
5 | public final class Seam { | 5 | public 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 | /** |