请教GIS最短路径输出。。。。。

Question

需要用java实现一个程序来求出根据所给出的起始节点和目标节点（在约束条件下，必须经过某些点，必须不经过某些点）来求出两个结点的最短路径。 
我有思路，但是转化为代码，还有些困难，在算法方面想请教一下大虾们。 
首先：实现本例的算法是否应选择Dsijkstra算法，有没有更优的算法？ 
第二：必须经过某些点的约束条件，我是这样想的，先求出起始节点到第一个约束节点的最短路径，再继续求出第一个约束点到第二个点的最短路径...一直到最后一个约束点到目标节点的最短路径。但是觉得这样效率不是很高。而且好像我试了好多次Dsijkstra算法实现的是一个结点到其他所有节点的最短路径，我只需要特定的两个节点的路径该怎么做呢？谢谢。 
第三：在必须不经过某些点的约束条件，我认为，先把要求不能经过的那些点删除掉，然后再求出最短路径。 
现在请求大虾支支招，要是有个带注释的源码参考参考那就更好了，谢谢。

Answer 1

http://www.cnblogs.com/kaixin110/archive/2007/08/10/850805.html

Answer 2

甚至不是太清楚GIS是什么。。 支持。

Answer 3

  大学是学GIS的，毕业后没有做本专业的工作，一直耿耿于怀，帮楼主顶一下。
  上面有楼说不太清楚GIS哦，我字面解释下，GIS就是 地理信息系统 。GIS在国内发展的比较晚，国外有做的很好的了，GoogleEath就是GIS的应用之一.

Answer 4

因为在学习JAVA，所以想用它来完成课程设计。

Answer 5

就是在每一走过一个节点后都去估计一下下一步走那条路更进，不通时退一下重走。 估计的方法heuristic algorithm的好坏将决定整个程序的效率。  这种serch通常是用于一些无法找到最佳方案时（无法找出确定的search规则）。 因为你的约束条件看起来没有什么规则。你这里的heuristic algorithm可能会用到Dsijkstra算法。  你自己查查吧。

Answer 6

本人不赞同这个方法，，原因：heuristic algorithm算法适用于迷宫方面的课题，而面对这个GIS，则不要的是寻找最短距离。。而用了heuristic algorithm算法，，如果第一条路能够直接取得通路的话，他就不会再去需求最佳的路径。。而使用第一找到的路径所以用heuristic algorithm来做最短路径效率不说，，本身就不一定能寻找到最短路径

Answer 7

heuristic algorithm：适用于求出唯一路径
Dsijkstra 使用于求出最短路径
而对于求最短路径，贪婪算法的Dsijkstra则应该是最佳的了，，
所以，我觉得LZ的方法应该还OK的。。
但有一个方法，，LZ可以试下，
就是利用JAVA的线程，，来优化你的效率

Answer 8

需要用java实现一个程序来求出根据所给出的起始节点和目标节点（在约束条件下，必须经过某些点，必须不经过某些点）来求出两个结点的最短路径。 不好意思，没看清问题。heuristic   algorithm：适用于求出唯一路径这样的说法是错的，heuristic   search是用来算出一条比较不错的路径在没有最佳方法算出最短路径。而不是仅用了求出唯一路径。

Answer 9

呵呵，好困啊~~
参考了一些资料和网上的代码。现在实现了从一个点到其他点的路径输出，先在程序中初始化了所需数据，然后进行算法。后来想实现从键盘输入任意的节点和权值，但是改过代码出现错，调试定位了错误的代码，但还没解决。先给出修改前的代码：
第一个类：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;
     }
 }
第二个类：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;
}
}第三个类：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;
}
}
}

Answer 10

只改了Dijkstra类，后两个没改。改了的类：
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！！！：）

Answer 11

最近一直在忙J2ME的手机游戏。终于在昨天搞定了，现在继续做这个最短路径问题，做完就可以结束数据结构的课程设计啦~~~~~~~~ 
大家帮忙看看偶的程序，还有400分，搞定这个问题，全部散掉，Thankyou~~~~~~~~~~~ 
：）

Answer 12

先回去研究一下 scauxie 的代码。
应该会有收获的。谢谢拉