两点之间最短路径算法

java程序两点之间最短路径算法_java 最短路径算法如何实现有向任意两点的最短路径...

2021-03-03 10:34:18

展开全部Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节e68a8462616964757a686964616f31333361316131点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。...

展开全部
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节e68a8462616964757a686964616f31333361316131点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点
代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain copy
public class Node {
private String name;
private Map child=new HashMap();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map getChild() {
return child;
}
public void setChild(Map child) {
this.child = child;
}
}
MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain copy
public class MapBuilder {
public Node build(Set open, Set close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
图的结构如下图所示：
Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain copy
public class Dijkstra {
Set open=new HashSet();
Set close=new HashSet();
Map path=new HashMap();//封装路径距离
Map pathInfo=new HashMap();//封装路径信息
public Node init(){
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
Set> pathInfos=pathInfo.entrySet();
for(Map.Entry pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance
minDis=distance;
res=child;
}
}
}
return res;
}
}
Main用于测试Dijkstra对象
[java] view plain copy
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}
本回答由提问者推荐
已赞过
已踩过<
你对这个回答的评价是？
评论
收起

收起

展开全文

java程序两点之间最短路径算法_如何计算网格中两点之间的最短路径

2021-03-03 10:34:55

这是使用BFS从(0,0)到(0，m-1)的矩阵中的最短路径的python实现 . 您可以将其更改为适合变量点 .n,m,k1,k2=[int(i) for i in input().split()]arr=[[int(j) for j in input().split()] for i in range(n)]x=[[-1 for ...

这是使用BFS从(0,0)到(0，m-1)的矩阵中的最短路径的python实现 . 您可以将其更改为适合变量点 .
n,m,k1,k2=[int(i) for i in input().split()]
arr=[[int(j) for j in input().split()] for i in range(n)]
x=[[-1 for i in range(m)] for j in range(n)]
x[0][0]=0
vis={}
q=[(0,0)]
while len(q)!=0:
curr=q[0]
rem=q.pop(0)
vis[curr]=True
r=curr[0]
c=curr[1]
if r-1>=0 and arr[r-1][c]==0:
if vis.get((r-1,c),-1)==-1 or vis[(r-1,c)]!=True:
q.append((r-1,c))
x[r-1][c]=x[r][c]+1
if r+1
if vis.get((r+1,c),-1)==-1 or vis[(r+1,c)]!=True:
q.append((r+1,c))
x[r+1][c]=x[r][c]+1
if c-1>=0 and arr[r][c-1]==0:
if vis.get((r,c-1),-1)==-1 or vis[(r,c-1)]!=True:
q.append((r,c-1))
x[r][c-1]=x[r][c]+1
if c+1
if vis.get((r,c+1),-1)==-1 or vis[(r,c+1)]!=True:
q.append((r,c+1))
x[r][c+1]=x[r][c]+1
#for i in x:
#print(i)
ans=x[0][m-1]
if ans==-1:
print(-1)
else:
print(ans)
输入矩阵应包含0 's and 1' s .  0表示可能的移动 .
n是行数 .
m是列数 .
arr是给定的矩阵 .
x是距离(0,0)的距离矩阵 .
vis是一个字典，如果访问该节点则给出一个布尔值 .
输出-1表示没有这样的路径可能 .

收起

展开全文

java程序两点之间最短路径算法_Java用Dijkstra算法实现地图两点的最短路径查询（Android版）...

2021-03-03 10:34:14

由于这是一个课程项目，时间比较急，而且自己不熟悉A*算法，所以参考网上的Dijkstra算法(http://blog.csdn.net/javaman_chen/article/details/8254309)的代码来实现了地图上任意两点的最短路径的查询。但该demo存在...

地图上实现最短路径的查询，据我了解的，一般用Dijkstra算法和A*算法来实现。由于这是一个课程项目，时间比较急，而且自己不熟悉A*算法，所以参考网上的Dijkstra算法(http://blog.csdn.net/javaman_chen/article/details/8254309)的代码来实现了地图上任意两点的最短路径的查询。但该demo存在一个很严重的错误，缺了两行非常关键的代码……
首先，来了解下Dijkstra算法：无向图的最短路径求解算法之——Dijkstra算法http://sbp810050504.blog.51cto.com/2799422/690803 。由此可以看出，Dijkstra算法的效率是很低的，它遍历的点很多，要以起始点为中心向外层层扩展，直到扩展到终点为止，所以数据量很少时不适合Dijkstra算法。处理该算法时，要特别注意在由一个点找到相邻该点最近点的时候，记得要将相邻的点的距离更新。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里是采用第二种方式，也就是采用的贪心法的算法策略，大概过程如下：
1.定义两个集合:open和close，open用于存储未遍历的节点，close用来存储已遍历的节点;
2.初始阶段，将初始节点放入close，其他所有节点放入open;
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并重新更新相邻点的距离，直至close包含所有子节点；
此方法由一个点遍历了其他所有点，所以可以知道该点到其他所有点的距离，时间复杂度很高。那个demo是一个一个数据初始化的，我将它改为用数组存储，然后用for循环来初始化，也就是将它封装成我需要的数据接口，并没有很大的优化。
算法核心只有两个函数：
/*** 获取与node最近的子节点*/
privateNode getShortestPath(Node node) {
Node res= null;int minDis =Integer.MAX_VALUE;
Map childs =node.getChild();//循环比较，找出离node最近的子节点
for(Node child : childs.keySet()) {if(open.contains(child)) {int distance =childs.get(child);if (distance 
minDis=distance;
res=child;
}
}
}returnres;
}
View Code
public voidcomputePath(Node start) {
Node nearest= getShortestPath(start);//取距离start节点最近的子节点,放入close
if (nearest == null) {return;
}
close.add(nearest);
open.remove(nearest);
Map childs =nearest.getChild();for(Node child : childs.keySet()) {if (open.contains(child)) {//如果子节点在open中
Integer newCompute = path.get(nearest.getName()) +childs.get(child);if (path.get(child.getName()) > newCompute) {//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
start.getChild().put(child, newCompute);
close.add(start);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+ "-" +child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
View Code
那个demo漏了两行代码，就是找到最近的路径后，没有更新相邻点的距离
start.getChild().put(child, newCompute);
close.add(start);
还有很多东西没优化，欢迎指出，一起学习！

收起

展开全文