1、问题描述
如下图,存在A~F六个地点,已知所有地点的相关关系(每个地点能到达的下一节点名称以及对应的路程);
计算某个起点(A~F)到某个终点(A~F)所需要的路程以及经过的地点顺序
2、节点类设置
public class Node {
public String name;
public Map<String,Integer> map = new HashMap<String,Integer>();
public List<Node> nodeList = new ArrayList<Node>();
public Node(){}
public Node(String name){
this.name = name;
}
public void setValue(String key,Integer value) {
map.put(key,value);
}
public void setNode(Node node) {
nodeList.add(node);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
3、设置节点之间的关系
public static Node setRoute() {
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
nodeA.setValue("B",10);
nodeA.setValue("C",14);
nodeA.setNode(nodeB);
nodeA.setNode(nodeC);
nodeB.setValue("A",10);
nodeB.setValue("C",11);
nodeB.setValue("D",8);
nodeB.setNode(nodeA);
nodeB.setNode(nodeC);
nodeB.setNode(nodeD);
nodeC.setValue("A",14);
nodeC.setValue("B",11);
nodeC.setValue("D",6);
nodeC.setValue("E",15);
nodeC.setNode(nodeA);
nodeC.setNode(nodeB);
nodeC.setNode(nodeD);
nodeC.setNode(nodeE);
nodeD.setValue("B",8);
nodeD.setValue("C",6);
nodeD.setValue("F",10);
nodeD.setNode(nodeB);
nodeD.setNode(nodeC);
nodeD.setNode(nodeF);
nodeE.setValue("C",15);
nodeE.setValue("F",12);
nodeE.setNode(nodeC);
nodeE.setNode(nodeF);
nodeF.setValue("D",10);
nodeF.setValue("E",12);
nodeF.setNode(nodeD);
nodeF.setNode(nodeE);
return nodeA;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
4、路线规划
public static void calculate(Node node,String stepStr,Integer steps,String endNode) {
if(!node.name.equals(endNode)) {
List<Node> nodeList = node.nodeList;
for (int i = 0; i < nodeList.size(); i++) {
Node n = nodeList.get(i);
if(stepStr.contains(n.name)) { continue; }
String stepStrT = stepStr + "->" + n.name;
int stepsT = steps + node.map.get(n.name);
calculate(n,stepStrT,stepsT,endNode);
}
}else {
System.out.println("finish:" + steps +"\t" + stepStr);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
5、完整类
package Test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class RoutePlanning {
public static int num = 0;
public static void main(String[] args) {
Node route = setRoute();
calculate(route,"A",0,"F");
System.out.println("execute times: " + num);
}
public static void calculate(Node node,String stepStr,Integer steps,String endNode) {
if(!node.name.equals(endNode)) {
List<Node> nodeList = node.nodeList;
for (int i = 0; i < nodeList.size(); i++) {
++num;
Node n = nodeList.get(i);
if(stepStr.contains(n.name)) { continue; }
String stepStrT = stepStr + "->" + n.name;
int stepsT = steps + node.map.get(n.name);
calculate(n,stepStrT,stepsT,endNode);
}
}else {
System.out.println("finish:" + steps +"\t" + stepStr);
}
}
public static Node setRoute() {
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
nodeA.setValue("B",10);
nodeA.setValue("C",14);
nodeA.setNode(nodeB);
nodeA.setNode(nodeC);
nodeB.setValue("A",10);
nodeB.setValue("C",11);
nodeB.setValue("D",8);
nodeB.setNode(nodeA);
nodeB.setNode(nodeC);
nodeB.setNode(nodeD);
nodeC.setValue("A",14);
nodeC.setValue("B",11);
nodeC.setValue("D",6);
nodeC.setValue("E",15);
nodeC.setNode(nodeA);
nodeC.setNode(nodeB);
nodeC.setNode(nodeD);
nodeC.setNode(nodeE);
nodeD.setValue("B",8);
nodeD.setValue("C",6);
nodeD.setValue("F",10);
nodeD.setNode(nodeB);
nodeD.setNode(nodeC);
nodeD.setNode(nodeF);
nodeE.setValue("C",15);
nodeE.setValue("F",12);
nodeE.setNode(nodeC);
nodeE.setNode(nodeF);
nodeF.setValue("D",10);
nodeF.setValue("E",12);
nodeF.setNode(nodeD);
nodeF.setNode(nodeE);
return nodeA;
}
public static class Node {
public String name;
public Map<String,Integer> map = new HashMap<String,Integer>();
public List<Node> nodeList = new ArrayList<Node>();
public Node(){}
public Node(String name){
this.name = name;
}
public void setValue(String key,Integer value) {
map.put(key,value);
}
public void setNode(Node node) {
nodeList.add(node);
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
6、结果
finish:37 A->B->C->D->F
finish:48 A->B->C->E->F
finish:51 A->B->D->C->E->F
finish:28 A->B->D->F
finish:43 A->C->B->D->F
finish:30 A->C->D->F
finish:41 A->C->E->F
execute times: 41
7、优化
优化:
每次遍历都判断所走路程,(详细记录已走的节点);如果当前路程超过记录中的最大路程,则停止;
选中记录列表中的最小路程重新往下走;重复该过程,直到到达终点后