请教GIS最短路径输出
时间:2008-05-13 05:40:44
来源:论坛整理 作者: 编辑:chinaitzhe
我有思路，但是转化为代码，还有些困难，在算法方面想请教一下大虾们。
首先：实现本例的算法是否应选择Dsijkstra算法，有没有更优的算法？
第二：必须经过某些点的约束条件，我是这样想的，先求出起始节点到第一个约束节点的最短路径，再继续求出第一个约束点到第二个点的最短路径...一直到最后一个约束点到目标节点的最短路径。但是觉得这样效率不是很高。而且似乎我试了好多次Dsijkstra算法实现的是一个结点到其他所有节点的最短路径，我只需要特定的两个节点的路径该怎么做呢？谢谢。
第三：在必须不经过某些点的约束条件，我认为，先把要求不能经过的那些点删除掉，然后再求出最短路径。
现在请求大虾支支招，要是有个带注释的源码参考参考那就更好了，谢谢。
网友回复:up...
网友回复:http://www.cnblogs.com/kaixin110/archive/2007/08/10/850805.html
网友回复:看了，研究ing
网友回复:这应该是动态规划的问题
网友回复:帮楼主顶一下
网友回复:甚至不是太清楚GIS是什么。。 支持。
网友回复:收此帖，回去帮你研究下
网友回复: 大学是学GIS的，毕业后没有做本专业的工作，一直耿耿于怀，帮楼主顶一下。
上面有楼说不太清楚GIS哦，我字面解释下，GIS就是 地理信息系统 。GIS在国内发展的比较晚，国外有做的很好的了，GoogleEath就是GIS的应用之一.
网友回复:不懂 不过个人以为假如算法知道了
拿用程序来表达的话用什么语言都是类似的。
网友回复:因为在学习JAVA，所以想用它来完成课程设计。
网友回复:heuristic search
网友回复:楼上可以将具体点吗？谢谢
网友回复:就是在每一走过一个节点后都去估计一下下一步走那条路更进，不通时退一下重走。 估计的方法heuristic algorithm的好坏将决定整个程序的效率。 这种serch通常是用于一些无法找到最佳方案时（无法找出确定的search规则）。 因为你的约束条件看起来没有什么规则。你这里的heuristic algorithm可能会用到Dsijkstra算法。 你自己查查吧。
网友回复:嗯，谢谢！：）
网友回复:
本人不赞同这个方法，，原因：heuristic algorithm算法适用于迷宫方面的课题，而面对这个GIS，则不要的是寻找最短距离。。而用了heuristic algorithm算法，，假如第一条路能够直接取得通路的话，他就不会再去需求最佳的路径。。而使用第一找到的路径。。。所以用heuristic algorithm来做最短路径效率不说，，本身就不一定能寻找到最短路径
网友回复:heuristic algorithm：适用于求出唯一路径
Dsijkstra 使用于求出最短路径
而对于求最短路径，贪婪算法的Dsijkstra则应该是最佳的了，，
所以，我觉得LZ的方法应该还OK的。。
但有一个方法，，LZ可以试下，
就是利用JAVA的线程，，来优化你的效率。。。
网友回复:好的！谢谢！我得认真研究研究才行。呵呵，谢谢你那么专心的帮忙。搞定了代码拿去和你交流交流。：）
网友回复:呵呵，，没问题，，我以前也和你一样
算法课上，，我也是每个算法、每个思想都自己去实现。。
网友回复:需要用java实现一个程序来求出根据所给出的起始节点和目标节点（在约束条件下，必须经过某些点，必须不经过某些点）来求出两个结点的最短路径。
不好意思，没看清问题。
heuristic algorithm：适用于求出唯一路径
这样的说法是错的，heuristic search是用来算出一条比较不错的路径在没有最佳方法算出最短路径。而不是仅用了求出唯一路径。
网友回复:楼主加油～实现好了能不能代码拿上来分享一下？
网友回复:恩 同意
网友回复:呵呵，好困啊~~
参考了一些资料和网上的代码。现在实现了从一个点到其他点的路径输出，先在程序中初始化了所需数据，然后进行算法。后来想实现从键盘输入任意的节点和权值，但是改过代码出现错，调试定位了错误的代码，但还没解决。先给出修改前的代码：
第一个类：
- Java code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ package cn.gis; import java.util.ArrayList; public class Dijkstra { static ArrayList<Side> map = null; static ArrayList<Integer> redAgg = null; static ArrayList<Integer> blueAgg = null; static Side[] parents = null; public static void main(String[] args) { // 初始化顶点集 int[] nodes = { 0, 1, 3, 2, 4, 5,6 }; // 初始化有向权重图 map = new ArrayList<Side>(); map.add(new Side(0, 1, 10)); map.add(new Side(0, 3, 30)); map.add(new Side(0, 4, 100)); map.add(new Side(1, 2, 50)); map.add(new Side(2, 4, 10)); map.add(new Side(3, 2, 20)); map.add(new Side(3, 4, 60)); map.add(new Side(4, 5, 50)); map.add(new Side(3, 5, 60)); map.add(new Side(5, 6, 10)); map.add(new Side(3, 6, 80)); // 初始化已知最短路径的顶点集，即红点集，只加入顶点0 redAgg = new ArrayList<Integer>(); redAgg.add(nodes[0]);//***************************************写成入口点； // 初始化未知最短路径的顶点集,即蓝点集 blueAgg = new ArrayList<Integer>(); for (int i = 1; i < nodes.length; i ) blueAgg.add(nodes[i]); // 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通 parents = new Side[nodes.length]; parents[0] = new Side(-1, nodes[0], 0);//************************************************************ for (int i = 0; i < blueAgg.size(); i ) { int n = blueAgg.get(i); parents[i 1] = new Side(nodes[0], n, getWeight(nodes[0], n));// } // 找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中 while (blueAgg.size() > 0) { MinShortPath msp = getMinSideNode(); if(msp.getWeight()==-1) msp.outputPath(nodes[0]); else msp.outputPath(); int node = msp.getLastNode(); redAgg.add(node); // 假如因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置 setWeight(node); } } /** * 得到一个节点的父节点 * * @param parents * @param node * @return */ public static int getParent(Side[] parents, int node) { if (parents != null) { for (Side nd : parents) { if (nd.getNode() == node) { return nd.getPreNode(); } } } return -1; } /** * 重新设置蓝点集中剩余节点的最短路径长度 * * @param preNode * @param map * @param blueAgg */ public static void setWeight(int preNode) { if (map != null && parents != null && blueAgg != null) { for (int node : blueAgg) { MinShortPath msp=getMinPath(node); int w1 = msp.getWeight(); if (w1 == -1) continue; for (Side n : parents) { if (n.getNode() == node) { if (n.getWeight() == -1 || n.getWeight() > w1) { n.setWeight(w1); n.setPreNode(preNode);//重新设置顶点的父顶点 break; } } } } } } /** * 得到两点节点之间的权重 * * @param map * @param preNode * @param node * @return */ public static int getWeight(int preNode, int node) { if (map != null) { for (Side s : map) { if (s.getPreNode() == preNode && s.getNode() == node) return s.getWeight(); } } return -1; } /** * 从蓝点集合中找出路径最小的那个节点 * * @param map * @param blueAgg * @return */ public static MinShortPath getMinSideNode() { MinShortPath minMsp = null; if (blueAgg.size() > 0) { int index = 0; for (int j = 0; j < blueAgg.size(); j ) { MinShortPath msp = getMinPath(blueAgg.get(j)); if (minMsp == null || msp.getWeight()!=-1 && msp.getWeight() < minMsp.getWeight()) { minMsp = msp; index = j; } } blueAgg.remove(index); } return minMsp; } /** * 得到某一节点的最短路径(实际上可能有多条,现在只考虑一条) * @param node * @return */ public static MinShortPath getMinPath(int node) { MinShortPath msp = new MinShortPath(node); if (parents != null && redAgg != null) { for (int i = 0; i < redAgg.size(); i ) { MinShortPath tempMsp = new MinShortPath(node); int parent = redAgg.get(i); int curNode = node; while (parent > -1) { int weight = getWeight(parent, curNode); if (weight > -1) { tempMsp.addNode(parent); tempMsp.addWeight(weight); curNode = parent; parent = getParent(parents, parent); } else break; } if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight()) msp = tempMsp; } } return msp; } }
第二个类：
- Java code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ package cn.gis; /** * @author Administrator * */ public class Side { private int preNode; private int node; private int weight; /** * * @param preNode:前向节点 * @param node：：:后向节点 * @param weight:权值 */ public Side(int preNode, int node, int weight) { this.preNode = preNode; this.node = node; this.weight = weight; } public int getPreNode() { return preNode; } public void setPreNode(int preNode) { this.preNode = preNode; } public int getNode() { return node; } public void setNode(int node) { this.node = node; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } }
第三个类：
- Java code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ package cn.gis; import java.util.ArrayList; /** * @author Administrator * */ public class MinShortPath { /** * nodeList:最短路径集 * weight:最短路径 */ private ArrayList<Integer> nodeList; private int weight; public MinShortPath(int node) { nodeList = new ArrayList<Integer>(); nodeList.add(node); weight = -1; } public ArrayList<Integer> getNodeList() { return nodeList; } public void setNodeList(ArrayList<Integer> nodeList) { this.nodeList = nodeList; } public void addNode(int node) { if (nodeList == null) nodeList = new ArrayList<Integer>(); nodeList.add(0, node); } public int getLastNode() { int size = nodeList.size(); return nodeList.get(size - 1); } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } public void outputPath() { outputPath(-1); } public void outputPath(int srcNode) { String result = "["; if (srcNode != -1) nodeList.add(srcNode); for (int i = 0; i < nodeList.size(); i ) { result = "" nodeList.get(i); if (i < nodeList.size() - 1) result = "->"; } result = "]:" weight; System.out.println(result); } public void addWeight(int w) { if (weight == -1) weight = w; else { weight = w; } } }
网友回复:只改了Dijkstra类，后两个没改。改了的类：
- Java code
Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ package cn.gis; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Dijkstra { static ArrayList<Side> map = null; static ArrayList<Integer> redAgg = null; static ArrayList<Integer> blueAgg = null; static Side[] parents = null; static int first; static int second; static int weight1; /** * * @param args */ public static void main(String[] args) { // 初始化顶点集 Scanner inSanner = new Scanner(System.in); System.out.println("Input the number of the nodes:");// 输入结点个数 int j = inSanner.nextInt(); int[] nodes = new int[j]; System.out.println("\ninput the nodes:");// 输入节点； // int[] nodes = { 0, 1, 3, 2, 4, 5,6 }; for (int i = 0; i < nodes.length; i ) { nodes[i] = inSanner.nextInt(); } // 初始化有向权重图 /* * map = new ArrayList<Side>(); map.add(new Side(0, 1, 10)); * map.add(new Side(0, 3, 30)); map.add(new Side(0, 4, 100)); * map.add(new Side(1, 2, 50)); map.add(new Side(2, 4, 10)); map.add(new * Side(3, 2, 20)); map.add(new Side(3, 4, 60)); map.add(new Side(4, 5, * 50)); map.add(new Side(3, 5, 60)); map.add(new Side(5, 6, 10)); * map.add(new Side(3, 6, 80)); */ System.out.println("input the starting point:");// 输入起始节点；； /** * * 排序nodes数组中的元素，原因是int k = Arrays.binarySearch(nodes, * p)执行前必须排序，否则返回值错误，在api中有说； */ Arrays.sort(nodes); int p = inSanner.nextInt(); int k = Arrays.binarySearch(nodes, p);// 寻找起始节点在nodes数组中的位置； /** * 交换nodes[0]与起始节点，使得nodes[0]中存的总是起始节点； */ int temp = nodes[k]; nodes[k] = nodes[0]; nodes[0] = temp; System.out.println("Input the number of the edgs"); int edges = inSanner.nextInt(); for (int i = 0; i < edges; i ) { System.out.println("Input the first node:"); first = inSanner.nextInt(); System.out.println("Input the sceond node:"); second = inSanner.nextInt(); System.out.println("Input the weight1:"); weight1 = inSanner.nextInt(); /** * 调试发现下面这句出问题，但不知错哪里？########################################################################### */ map.add(new Side(first, second, weight1)); } // 初始化已知最短路径的顶点集，即红点集，只加入顶点0 redAgg = new ArrayList<Integer>(); redAgg.add(nodes[0]); // 初始化未知最短路径的顶点集,即蓝点集 blueAgg = new ArrayList<Integer>(); for (int i = 1; i < nodes.length; i ) blueAgg.add(nodes[i]); // 初始化每个顶点在最短路径中的父结点,及它们之间的权重,权重-1表示无连通 parents = new Side[nodes.length]; parents[0] = new Side(-1, nodes[0], 0); for (int i = 0; i < blueAgg.size(); i ) { int n = blueAgg.get(i); parents[i 1] = new Side(nodes[0], n, getWeight(nodes[0], n));// } // 找从蓝点集中找出权重最小的那个顶点,并把它加入到红点集中 while (blueAgg.size() > 0) { MinShortPath msp = getMinSideNode(); if (msp.getWeight() == -1) msp.outputPath(nodes[0]); else msp.outputPath(); int node = msp.getLastNode(); redAgg.add(node); // 假如因为加入了新的顶点,而导致蓝点集中的顶点的最短路径减小,则要重要设置 setWeight(node); } } /** * 得到一个节点的父节点 * * @param parents * @param node * @return */ public static int getParent(Side[] parents, int node) { if (parents != null) { for (Side nd : parents) { if (nd.getNode() == node) { return nd.getPreNode(); } } } return -1; } /** * 重新设置蓝点集中剩余节点的最短路径长度 * * @param preNode * @param map * @param blueAgg */ public static void setWeight(int preNode) { if (map != null && parents != null && blueAgg != null) { for (int node : blueAgg) { MinShortPath msp = getMinPath(node); int w1 = msp.getWeight(); if (w1 == -1) continue; for (Side n : parents) { if (n.getNode() == node) { if (n.getWeight() == -1 || n.getWeight() > w1) { n.setWeight(w1); n.setPreNode(preNode);// 重新设置顶点的父顶点 break; } } } } } } /** * 得到两点节点之间的权重 * * @param map * @param preNode * @param node * @return */ public static int getWeight(int preNode, int node) { if (map != null) { for (Side s : map) { if (s.getPreNode() == preNode && s.getNode() == node) return s.getWeight(); } } return -1; } /** * 从蓝点集合中找出路径最小的那个节点 * * @param map * @param blueAgg * @return */ public static MinShortPath getMinSideNode() { MinShortPath minMsp = null; if (blueAgg.size() > 0) { int index = 0; for (int j = 0; j < blueAgg.size(); j ) { MinShortPath msp = getMinPath(blueAgg.get(j)); if (minMsp == null || msp.getWeight() != -1 && msp.getWeight() < minMsp.getWeight()) { minMsp = msp; index = j; } } blueAgg.remove(index); } return minMsp; } /** * 得到某一节点的最短路径(实际上可能有多条,现在只考虑一条) * * @param node * @return */ public static MinShortPath getMinPath(int node) { MinShortPath msp = new MinShortPath(node); if (parents != null && redAgg != null) { for (int i = 0; i < redAgg.size(); i ) { MinShortPath tempMsp = new MinShortPath(node); int parent = redAgg.get(i); int curNode = node; while (parent > -1) { int weight = getWeight(parent, curNode); if (weight > -1) { tempMsp.addNode(parent); tempMsp.addWeight(weight); curNode = parent; parent = getParent(parents, parent); } else break; } if (msp.getWeight() == -1 || tempMsp.getWeight() != -1 && msp.getWeight() > tempMsp.getWeight()) msp = tempMsp; } } return msp; } }
今天明天要去兼职，晚上回来才能做了...大家帮忙看看啊~~
而且先在离还好远啊。先在实现的是没有两种约束情况的简单代码。还要继续研究算法！！！GABADE！！！：）
网友回复:up,up...
网友回复:up...大家帮帮忙哦~~~
网友回复:帮忙看看哦~~~
网友回复:该回复于2008-05-01 06:22:48被版主删除
网友回复:最近一直在忙J2ME的手机游戏。终于在昨天搞定了，现在继续做这个最短路径问题，做完就可以结束数据结构的课程设计啦~~~~~~~~
大家帮忙看看偶的程序，还有400分，搞定这个问题，全部散掉，Thankyou~~~~~~~~~~~
：）
关键字：请教,GIS,路径,输出,
下一篇：下面没有链接了
文章评论
共有 0 位网友发表了评论 此处只显示部分留言 点击查看完整评论页面