再说下算法部分。
我参考了网上的一些算法。采用到的是 floyd算法。参考地址http://www.ddvip.com/tech/1000140659.html
嫌弃它广告太多，我还是把图抠过来了，如下：
再顺路搬一段文字过来:
初始状态：S是记录各个顶点间最短路径的矩阵。
第1步：初始化S。
矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。实际上，就是将图的原始矩阵复制到S中。
注:a[i][j]表示矩阵S中顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
第2步：以顶点A(第1个顶点)为中介点，若a[i][j] > a[i][0]+a[0][j]，则设置a[i][j]=a[i][0]+a[0][j]。
以顶点a[1]6，上一步操作之后，a[1][6]=∞；而将A作为中介点时，(B,A)=12，(A,G)=14，因此B和G之间的距离可以更新为26。
同理，依次将顶点B,C,D,E,F,G作为中介点，并更新a[i][j]的大小。
好了，算法的核心也就出来了，一直更新一个矩阵。
那么先来定义一些变量吧：
private static final int INF = Integer.MAX_VALUE; // 最大值，处理两点之间无线断的权值。 int pointNum=points.size(); int n=pointNum;//总点数，从数据读取的 int path[][]=new int[n+1][n+1];//路径矩阵，记录点的前驱 int map[][]=new int[pointNum+1][pointNum+1];//构造权值矩阵 int dist[][]=map;//最终的最短路径矩阵 其实也可以之间用map
接下来是核心算法代码：
//算法算出所有点对点最短路径
for(int k=1; k<=n; k++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
// 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
if(!(dist[i][k]==INF||dist[k][j]==INF)&&dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
// "i到j最短路径"对应的路径，经过k
path[i][k] = i;
path[i][j] = path[k][j];
}
}
}
}
最终的写在后台的控制器的代码为:
@RequestMapping(value = "/test",produces="application/json;charset=utf-8", method = {RequestMethod.POST,RequestMethod.GET})
public @ResponseBody JSONObject test(HttpSession session,
@RequestParam(required = false) int from,
@RequestParam(required = false) int to)
{
JSONObject obj=new JSONObject();
// 找到所有的点
PointDAO pdao=new PointDAOImpl();
LineDAO ldao=new LineDAOImpl();
List<Point> points=pdao.findAllPoint();
int pointNum=points.size();
int n=pointNum;//总点数，从数据读取的
int path[][]=new int[n+1][n+1];//路径矩阵，记录点的前驱
int map[][]=new int[pointNum+1][pointNum+1];//构造权值矩阵
// 读取数据库，赋初值
for(int i=1;i<=pointNum;i++) {
for(int j=1;j<=pointNum;j++) {
Line line=ldao.find(i, j);
if(i==j) {
map[i][j]=0;//自己到自己距离为0
}
else if(line==null) {//不存在此路径，权值为无穷大
map[i][j]=INF;
}
else {
map[i][j]=line.getLenth();
}
}
}
// 打印输入的矩阵，便于控制台查看
System.out.println("打印输入的矩阵");
for(int i=1;i<=pointNum;i++) {
for(int j=1;j<=pointNum;j++) {
System.out.print(map[i][j]+"|");
}
System.out.println("");
}
// 定义路径前驱
int dist[][]=map;//最终的最短路径矩阵
for(int i=1; i<=n ; i++){
for(int j=1; j<= n; j++){
if(map[i][j]==0){
path[i][j] = -1;//表示 i -> j 不通
}else{
path[i][j] = i;// 表示 i -> j 前驱为 i
}
}
}
// 算法算出所有点对点最短路径
for(int k=1; k<=n; k++) {
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
// 如果经过下标为k顶点路径比原两点间路径更短，则更新dist[i][j]和path[i][j]
if(!(dist[i][k]==INF||dist[k][j]==INF)&&dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
// "i到j最短路径"对应的路径，经过k
path[i][k] = i;
path[i][j] = path[k][j];
}
}
}
}
System.out.println("打印最终的矩阵");
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
System.out.print(dist[i][j]+"|");
}
System.out.println("");
}
obj.put("lenth", dist[from][to]);
// 倒序输出
List<Point> p=new ArrayList<Point>();
p.add(pdao.find(to));
while(path[from][to]!=from) {
System.out.print(path[from][to] +"----");
p.add(pdao.find(path[from][to]));
to = path[from][to];
}
p.add(pdao.find(from));
Collections.reverse(p);
obj.put("path", p);
return obj;
}</pre>
前台传过来两个参数，起始点和终结点，算法算出这两个点的最短路径以及经过的点，然后将结果存入JSONObject对象，传给前台。
下面是前台ajax请求的代码部分：
jQuery(document).on('click', ".searchPath", function() {
var data={
from:$("#searchFrom").val(),
to:$("#searchTo").val()
}
jQuery.ajax({
type: 'POST',
url: "test",
data:data,
dataType: 'json',
success: function(json) {
var canvers=document.getElementById('mycanver');
var cxt=canvers.getContext('2d');
cxt.save();
cxt.strokeStyle="red";
cxt.translate(0.5,0.5);
cxt.lineWidth = 2;
cxt.beginPath();
cxt.moveTo(json.path[0].x, json.path[0].y);
var text="最短路径为："+json.path[0].name;
for(var i=1;i<json.path.length;i++){
cxt.lineTo(json.path[i].x,json.path[i].y);
text=text+"——>"+json.path[i].name;
}
$("#control").html(text+"\<br\>");
$("#control").append("最短路径为："+json.lenth+"米\<br\>");
$("#control").append("步行大约用时："+Math.ceil(json.lenth/60)+"分钟")
cxt.stroke();
cxt.restore();
}
});
});
差不多了就缺整体代码了，最后再更新。
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于