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: import java.util.HashSet;
19: import java.util.Set;
20:
21: public class ShortestPathAcyclic { 22:
23: private static final int INF = Integer.MAX_VALUE;
24:
25: // nodes (s,x,y,t) = {0,1,2,3}, so (s,x) = 3 means d[0][1] = 3 26: private static int[][] distance = { 27: { INF, 3, 5, INF }, 28: { INF, INF, 1, 8 }, 29: { INF, INF, INF, 5 }, 30: { INF, INF, INF, INF } 31: };
32:
33: private static Set<Integer> possibleNextNodes(int node) { 34: Set<Integer> result = new HashSet<Integer>();
35: for (int i = 0; i < distance[node].length; i++) { 36: if (distance[node][i] != INF) { 37: result.add(new Integer(i));
38: }
39: }
40: return result;
41: }
42:
43: public static double f(int currentNode){ 44: if(currentNode==3) return 0.0;
45: else{ 46: Set<Integer> possibleSuccessors = possibleNextNodes(currentNode);
47: double min = Double.MAX_VALUE;
48: for(Integer d : possibleSuccessors){ 49: double dis = distance[currentNode][d]+f(d);
50: if(dis<min) { 51: min = dis;
52: }
53: }
54: return min;
55: }
56: }
57:
58: /**
59: * @param args
60: */
61: public static void main(String[] args) { 62: double shortest = f(0);
63: System.out.println(shortest);
64: }
65:
66: }