偶然讨论到图,才发工作过程中这些摸的真少;竟然隐约勾起了大学时代的回忆,
嗯,基本是魔兽争霸和魔兽世界;
突然兴起,重新写写,算是记念;
求A到D点,与B到D点的最短路径
采用Dijkstra算法,用map(java就是好),存储每个子递归过程的中间结果集,确保不会重复计算;
基于此(有cache的 dijkstra实现 ),可任意实现取任意点到点的最短路径及所有路径,及所有点互相之间所有路径及最短路径问题;
递归原理,求A到D的最短路径,即求A相连点到D的不包括A点(已访问点集合)的最短路径加上A到相连点路径的最小值;
针对每个子递归,对起点和终点与已经访问点集合做HashMap的cache;
data.txt
A B 3
A E 4
B H 1
B C 5
H D 6
C D 2
E G 1
E F 4
G I 3
I F 1
G C 2
F C 2
点与点的关系在data.txt中描述, "A B 3" 表示A与B之间无向连通,距离为3
Data
public class Data {
//存储结点
private Map<String, Node> nodes = new HashMap<String, Node>();
//存储结点间距离
private Distance dis = new Distance();
//从文件中读取
public Data(String file) throws IOException{
InputStream instream = Thread.currentThread().getContextClassLoader().getResourceAsStream(file);
BufferedReader reader = new BufferedReader(new InputStreamReader(instream));
String line = null;
while ((line = reader.readLine()) != null) {
String[] items = line.trim().split(" ");
String nodeName1 = items[0];
String nodeName2 = items[1];
int length = Integer.valueOf(items[2]);
Node node1 = nodes.get(nodeName1);
if (node1 == null) {
node1 = new Node(nodeName1);
nodes.put(nodeName1, node1);
}
Node node2 = nodes.get(nodeName2);
if (node2 == null) {
node2 = new Node(nodeName2);
nodes.put(nodeName2, node2);
}
node1.connect(node2);
node2.connect(node1);
dis.put(nodeName1 + nodeName2, length);
dis.put(nodeName2 + nodeName1, length);
}
reader.close();
}
public Map<String, Node> getNodes() {
return nodes;
}
public Distance getDis() {
return dis;
}
}
Node:
public class Node {
private String name;
private Set<Node> connected = new HashSet<Node>();
public Node(String name){
this.name = name;
}
public void connect(Node node) {
this.connected.add(node);
}
public boolean isConnected(Node node) {
return connected.contains(node);
}
public Iterator<Node> getConnected() {
return this.connected.iterator();
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String toString() {
return this.getName();
}
}
Path
public class Path {
private Integer dis = -1;
private LinkedList<Node> path = new LinkedList<Node>();
public Integer getDis() {
return dis;
}
public void setDis(Integer dis) {
this.dis = dis;
}
public LinkedList<Node> getPath() {
return path;
}
}
Distance
public class Distance {
private Map<String, Integer> distance = new HashMap<String, Integer>();
public void put(String relation, int distance) {
this.distance.put(relation, distance);
}
public Integer get(String relation) {
Integer rs = distance.get(relation);
return rs;
}
public Integer get(Node a, Node b) {
return this.get(a.getName() + b.getName());
}
}
主算法
public class ComputeShort {
private Data data;
private EasyCache cache = new EasyCache();
private Path getShortDis(Node a, Node b, Set<Node> visited) {
//Set里的值是和放入顺序无关的固定顺序,这里恰好可以做cache的key
String key = a.toString() + b.toString() + visited;
Path rs = (Path) cache.get(key);
if (rs != null) {
System.out.println("read from cache : " + key);
return rs;
}
//cache里没有则计算
rs = new Path();
//访问过了则返回
if (visited.contains(a)) {
cache.put(key, rs);
return rs;
} else {
visited.add(a);
rs.getPath().add(a);
}
//如果是相连的直接返回结果
if (a.isConnected(b)) {
rs.getPath().add(b);
rs.setDis(data.getDis().get(a, b));
cache.put(key, rs);
return rs;
} else {
//否则递归调用
Iterator<Node> nodes = a.getConnected();
int tempRs = -1;
LinkedList<Node> path_temp = null;
while (nodes.hasNext()) {
Node temp = nodes.next();
Integer dis = -1;
Set<Node> visted_child = new HashSet<Node>();
visted_child.addAll(visited);
Path child = getShortDis(temp, b, visted_child);
if (child.getDis() == -1) continue;
dis = data.getDis().get(a, temp) + child.getDis();
if (tempRs == -1 || dis < tempRs) {
tempRs = dis;
path_temp = child.getPath();
}
}
if (path_temp != null) rs.getPath().addAll(path_temp);
if (tempRs != -1) rs.setDis(tempRs);
cache.put(key, rs);
return rs;
}
}
public Data getData() {
return data;
}
public void setData(Data data) {
this.data = data;
}
public Path getShort(String a, String b) {
Node nodeA = data.getNodes().get(a);
Node nodeB = data.getNodes().get(b);
Path p = getShortDis(nodeA, nodeB, new HashSet<Node>());
return p;
}
}
Cache
public class EasyCache {
private Map<String, Object> map = new HashMap<String, Object>();
public void put(String key, Object value) {
this.map.put(key, value);
}
public Object get(String key) {
return map.get(key);
}
}
public class Main {
public static void main(String[] args) throws Exception {
ComputeShort hello = new ComputeShort();
Data data = new Data("data.txt");
hello.setData(data);
Path p = hello.getShort("A", "D");
System.out.println(p.getPath() + " = " + p.getDis());
p = hello.getShort("B", "D");
System.out.println(p.getPath() + " = " + p.getDis());
}
}
运行结果
read from cache : CD[E, F, I, A, G]
read from cache : ED[E, F, I, A, G]
read from cache : ID[E, F, I, A, G]
[A, E, G, C, D] = 9
read from cache : CD[E, F, I, A, G, B]
read from cache : ED[E, F, I, A, G, B]
read from cache : ID[E, F, I, A, G, B]
[B, C, D] = 7
分享到:
相关推荐
java 最短路径 问题 动态规划java 最短路径 问题 动态规划
用java实现的求迷宫最短路径的算法源代码,代码中有大量注释,容易看懂
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
java实现最短路径搜索,并选出最短路径
迪杰斯特拉算法实现K条最短路径! 用java语言进行实现!
用java实现的最短路径问题,里面具体实现了一张图的查询
算法实验,实现了图的单元最短路径的查找,希望有所帮助
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 [1] 确定终点的...
采用的是分枝定界算法,效率较低
JAVA版动态规划解决最短路径问题 啊
用java语言和Diskstra算法编写的求最短路径程序。可求得最短路径的长度和路径。
* (有向)带权图的单源点最短路径算法 */ package dsa; public class BestFSDijkstra extends BestFS { //构造方法 public BestFSDijkstra(Graph g) { super(g); } //更新尚未访问的顶点到源点的最短距离 ...
基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的Dijkstra最短路径寻径的实现..zip基于Java实现的...
标题: 单元最短路径 时 限: 1000 ms 内存限制: 10000 K 总时限: 3000 ms 描述: 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个整数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有...
本程序可以应用文件操作,通过读取文件获得输入并且将输出结果以文件形式存在目录文件夹下
用Java编写的最短路径代码,非常有用的东西,希望大家多多支持。
最短路径算法java 单源点最短路径Dijkstra算法的JAVA实现
基于gdal的最短路径计算方式,参考QGIS实现的,cal文件夹是计算类,其他几个文件是QGIS封装
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个整数。另外,还给定 V 中的一个顶点,...现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
该文档讲述了java语言编写的实现最短路径的算法,简单易实现