dongtaiguihua.rar_Java3年guihua_dongtaiguihua_最短路径

package 动态规划; import java.util.*; /** * 用动态规划法求出最优路径 * @author zqc * */ public class DynamicSolveTrianglePath { private String[][] str_triangle = null; private Node[][] triangle_nodes = null; private List nodes; private List paths; // 节点 static class Node { private int value; private List path = new Vector(); public List getPath() { return path; } public void setPath(List p) { path = p; } // n=(0,0) or (0,1) or (2,2) public void addPath(String n) { path.add(n); } public void addPath(List pa) { path.addAll(pa); } public int getValue() { return value; } public void setValue(int value) { this.value = value; } } public DynamicSolveTrianglePath() { initNodes(); findPath(); } // 从根节点开始,逆向推解出到达所有节点的最佳路径 private void initNodes() { this.str_triangle = ReadTriangle.getTriangle(); triangle_nodes = new Node[str_triangle.length][]; nodes = new Vector(); for (int i = 0; i < str_triangle.length; i++) { triangle_nodes[i] = new Node[str_triangle[i].length]; for (int j = 0; j < str_triangle[i].length; j++) { String currentPath = "(" + i + "," + j + ")"; Node n = new Node(); if (i == 0 && j == 0) { n.setValue(c(str_triangle[0][0])); n.addPath(currentPath); triangle_nodes[i][j] = n; continue; } // 左右边界节点 if ((j == 0 || j == str_triangle[i].length - 1)) { if (i == 1) {// 第2行的节点 int value = c(str_triangle[0][0]) + c(str_triangle[i][j]); List ph = triangle_nodes[0][0].getPath(); n.addPath(ph); n.addPath(currentPath); n.setValue(value); ph = null; } else {// 0,1行以下的其他边界节点 int value = j == 0 ? c(str_triangle[i][j]) + triangle_nodes[i - 1][j].getValue() : c(str_triangle[i][j]) + triangle_nodes[i - 1][j - 1] .getValue(); List ph = j == 0 ? triangle_nodes[i - 1][j].getPath() : triangle_nodes[i - 1][j - 1].getPath(); n.addPath(ph); n.addPath(currentPath); n.setValue(value); } } else {// 除边界节点外其他节点 Node node1 = triangle_nodes[i - 1][j - 1]; Node node2 = triangle_nodes[i - 1][j]; Node bigger = max(node1, node2); List ph = bigger.getPath(); n.addPath(ph); n.addPath(currentPath); int val = bigger.getValue() + c(str_triangle[i][j]); n.setValue(val); } triangle_nodes[i][j] = n; n = null; }// end of for j }// end of for i } private Node max(Node node1, Node node2) { int i1 = node1.getValue(); int i2 = node2.getValue(); return i1 > i2 ? node1 : node2; } private int c(String s) { return Integer.parseInt(s.trim()); } // 找出最佳路径 private void findPath() { if (this.triangle_nodes == null) return; int max = 0; int mi = 0; int mj = 0; for (int i = 0; i < triangle_nodes.length; i++) { for (int j = 0; j < triangle_nodes[i].length; j++) { int t = triangle_nodes[i][j].getValue(); if (t > max) { max = t; mi = i; mj = j; } } } System.out.println("Max Path:" + triangle_nodes[mi][mj].getPath()); System.out.println("Max Value:" + max); } public static void main(String[] args) throws Exception { DynamicSolveTrianglePath dsp = new DynamicSolveTrianglePath(); } }