1: /*
2: * Copyright (C) 2013 changedi
3: *
4: * Licensed under the Apache License, Version 2.0 (the "License");
5: * you may not use this file except in compliance with the License.
6: * You may obtain a copy of the License at
7: *
8: * http://www.apache.org/licenses/LICENSE-2.0
9: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16: package com.jybat.dp;
17:
18: public class APSP { 19:
20: private static final int INF = Integer.MAX_VALUE;
21:
22: // nodes (s,x,y,t) = {0,1,2,3}, so (s,x) = 3 means d[0][1] = 3 23: private static int[][] distance = { 24: { INF, 5, 3, INF }, 25: { INF, INF, 2, 5 }, 26: { INF, 1, INF, 8 }, 27: { INF, INF, INF, INF } 28: };
29:
30: private static int maxNodeIndex = distance.length-1;
31:
32: private static int[] possibleSuccessors = { 0, 1 }; 33:
34: public static double f(int k, int p, int q) { 35: if (k == 0 && p == q)
36: return 0;
37: if (k == 0 && p != q)
38: return distance[p][q];
39: double min = Double.MAX_VALUE;
40: for (int d : possibleSuccessors) { 41: double t = (1 - d) * f(k - 1, p, q) + d * f(k - 1, p, k) + d
42: * f(k - 1, k, q);
43: if (t < min)
44: min = t;
45: }
46: return min;
47: }
48: /**
49: * @param args
50: */
51: public static void main(String[] args) { 52: System.out.println(f(maxNodeIndex,0,3));
53: }
54:
55: }