JAVA版最短路径

偶然讨论到图,才发工作过程中这些摸的真少;竟然隐约勾起了大学时代的回忆,
嗯,基本是魔兽争霸和魔兽世界;

突然兴起,重新写写,算是记念;

求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

评论

1 楼 zhongmingmao 2012-08-30  

十几万条边，一万多个节点的测试用例，电脑内存会溢出，有什么建议么？