`
yfyh87
  • 浏览: 35465 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
文章分类
社区版块
存档分类
最新评论

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


5
4
分享到:
评论
1 楼 zhongmingmao 2012-08-30  
十几万条边,一万多个节点的测试用例,电脑内存会溢出,有什么建议么?

相关推荐

    java 最短路径 问题 动态规划

    根据给定的信息,本文将详细解释Java实现的最短路径问题动态规划算法。该程序的主要目的是寻找图中各个节点到指定终点的最短路径,并输出每个节点到终点的最短距离以及达到这些最短距离时的决策路径。 ### 1. 问题...

    java实现的求迷宫最短路径算法

    本主题聚焦于使用Java实现求解迷宫最短路径的算法。在给定的压缩包中,包含两个文件:ShortPath.java和Position.java,它们分别代表了核心算法和坐标位置的数据结构。 首先,`Position.java`文件可能定义了一个类,...

    Floyd最短路径java实现

    运行上述Java程序并输出结果后,检查每个顶点对之间的最短路径是否正确。 总结,Floyd最短路径算法通过动态规划的思想,逐步增加中间节点,逐步完善最短路径信息。在Java中实现时,主要利用了二维数组来存储图的...

    用java通过文件操作实现最短路径问题

    下面我们将详细讨论如何在Java中通过文件操作来解决最短路径问题。 首先,我们需要了解最短路径算法。其中,Dijkstra算法和Floyd-Warshall算法是两种常用的方法。Dijkstra算法适用于单源最短路径问题,而Floyd-...

    java 无向图所有最短路径算法的实现

    本项目以Java语言实现了求解无向图所有最短路径的算法。 1. **Dijkstra算法** Dijkstra算法是最常用的单源最短路径算法,用于找到图中一个顶点到其他所有顶点的最短路径。在无向图中,Dijkstra算法通过维护一个...

    java最短路径

    java实现最短路径搜索,并选出最短路径

    java实现的最短路径问题

    在计算机科学中,最短路径...总之,Java实现的迪杰斯特拉算法为我们提供了解决最短路径问题的有效工具。通过理解算法的工作原理和Java实现细节,我们可以灵活地应用于各种图结构问题,为软件开发和数据分析带来便利。

    用Java编写的最短路径代码

    本篇文章将深入探讨如何使用Java编程语言解决最短路径问题,并结合提供的文件"最短路径"进行分析。 首先,我们要了解几种常见的最短路径算法,包括Dijkstra算法、Bellman-Ford算法以及Floyd-Warshall算法。其中,...

    基于gdal 最短路径计算

    在IT行业中,地理信息系统(GIS)的开发与应用经常涉及到空间数据处理,其中包括最短路径的计算。GDAL(Geospatial Data Abstraction Library)是一个强大的开源库,它提供了多种功能,包括读取、写入和操作各种地理...

    最短路径(Java)

    本文将深入探讨如何使用Java语言和Dijkstra算法来解决最短路径问题。 Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻在1956年提出的一种单源最短路径算法。它能够找到一个加权有向或无向图中,从源节点到其他...

    用java写的查询某市地铁的最短路径,递归算法

    在这个特定的项目中,我们有一个Java程序,它使用递归算法来解决查询某市地铁的最短路径的问题。递归算法是一种强大的工具,它通过将大问题分解为更小的相似子问题来解决复杂的问题。 首先,我们要理解什么是递归。...

    java K最短路径

    Java 实现K最短路径算法详解 在图论和计算机科学中,寻找网络中的最短路径是一个常见的问题。K最短路径(K Shortest Paths,KSP)算法旨在找到源节点到目标节点的前K条最短路径。迪杰斯特拉(Dijkstra)算法通常...

    Java实现图的最短路径问题

    算法实验,实现了图的单元最短路径的查找,希望有所帮助

    图的最短路径.xls

    最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 [1] 确定终点的...

    基于Java的最短路径问题的解决

    采用的是分枝定界算法,效率较低

    分支限界法求解单源最短路径

    `BBShortest.java`可能是主算法实现,使用分支限界法求解单源最短路径。BB(Branch and Bound,分支与边界)的"分支"指的是在搜索空间中扩展新的节点,"边界"则是指通过限界函数设置的约束条件,用于避免无效的搜索...

    从某个源点到其于各顶点的最短路径

    ### 单源最短路径问题解析 #### 一、引言 在图论与计算机科学领域,寻找从一个源点到图中其他所有顶点的最短路径问题被广泛研究,这种问题通常被称为“单源最短路径问题”。这类问题在实际应用中具有重要意义,例如...

    基于Java的最短路径算法实现 k-shortest-paths.zip

    "基于Java的最短路径算法实现 k-shortest-paths.zip" 是一个压缩包,其中包含了用Java编程语言实现的一种算法,该算法旨在找到图中两个节点之间的多条最短路径,即k最短路径(K-Shortest Paths, KSP)。在这个讨论中...

    动态规划解决最短路径问题

    JAVA版动态规划解决最短路径问题 啊

Global site tag (gtag.js) - Google Analytics