最短路径算法java

发布时间: 2022-06-30 03:09:43

1. 求最短路径算法

java">importjava.awt.*;
importjava.util.HashSet;
importjava.util.Random;

classexample2{


privatestaticPoint[]mTestPoints;

//已知平面上N点坐标,求遍历所有点的最短路径.
publicstaticvoidmain(String[]args){

//两点之间的距离d=√(a^2+b^2)其中a=|x1–x2|;b=|y1-y2|
//都是简单的正相关函数,距离最短那么需要a+b最小
//n个点需要求C(n,2)次
//其实java提供了两点之间距离的Api咱们直接使用即可

generateTestPoints();

doubleminDistance=Double.MAX_VALUE;
for(inti=0;i<mTestPoints.length;i++){
//两两计算,数组中每个点只跟后面的点求距离
for(intj=i+1;j<mTestPoints.length;j++){
doubledistance=mTestPoints[i].distance(mTestPoints[j]);
if(distance<minDistance){
minDistance=distance;
}
}
}
//得到结果
System.out.println("最短距离为:"+minDistance);
}

(){

//随机生成10个点的集合,为了去重使用hashSet
Randomrandom=newRandom();
HashSet<Point>mPointSet=newHashSet<>();
for(inti=0;i<10;i++){
booleanadd=mPointSet.add(newPoint(random.nextInt(100),random.nextInt(100)));
if(!add){
--i;
}
}
mTestPoints=mPointSet.toArray(newPoint[10]);
}
}

2. 求大佬用java帮我实现dijkstra算法，单源最短路径

python">import heapq
from collections import defaultdict
edges = [["A","B"],["A","D"],["A","E"],["B","C"],["C","E"],["D","E"],["D","C"]]
dist = [10,30,100,50,10,60,20]
res = []
def dijkstra(e,dist,start,end):
‍  hm = defaultdict(list)
‍  for i in range(len(e)):
‍  ‍  hm[e[i][0]].append((e[i][1],dist[i]))
‍  r = {}
‍  r[start] = 0
‍  q = [(0,start,[start])]
‍  while q:
‍  ‍  dis,node,res = heapq.heappop(q)
‍  ‍  if node == end:
‍  ‍  ‍  return dis,res
‍  ‍  for u,v in hm[node]:
‍  ‍  ‍  t = dis+v
‍  ‍  ‍  if u not in r or t < r[u]:
‍  ‍  ‍  ‍  r[u] = t
‍  ‍  ‍  ‍  heapq.heappush(q,(t,u,res+[u]))
‍  return 0,[]
dijkstra(edges,dist,"A","E")

3. 有什么无权无向图的最短路径算法比较好，求一个用java实现的

有什么无权无向图的最短路径算法比较好

带权图也分有向和无向两种，基本的算法可以看看书咯。带权的无向图的最短路径又叫最小生成树，Prim算法和Kruskal算法；带权的有向图的最短路径算法有迪杰斯特拉算法和佛洛依德算法；

String[]s={"January","February","March","April","May","June","July","August","September","October","November","December"};
System.out.print("请输入数字（1-12）：");
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
Stringstr=br.readLine();
intm=Integer.parseInt(str);
if(m<=0||m>=13)
{

4. java，最短路径问题

这个的东西已经忘记了。记得是学离散数学的时候有讲过，lz还是自己去找本专业书看看吧

5. Java 最短路径算法如何实现有向任意两点的最短路径

http://blog.csdn.net/javaman_chen/article/details/8254309

6. 如何求解最短路径（求Java程序实现）

那你就别弄最短的。你把所有的路径都查出来。然后比较长短，然后从短到长依次打印出来不就行了嘛。。

7. JAVA求10个景点间各个景点的最短路径图随便话距离随便求代码

最有效，切不复杂的方法使用Breadth First Search (BFS). 基本代码如下（伪代码）。因为BFS不用递归，所以可能会有点难理解。

public Stack findPath(Vertex 起始景点, Vertex 目标景点){
Queue <Vertex> q = new Queue<Vertex>();
s.enqueue(起始景点);
Vertex 当前位置;
while(!s.isEmpty()){
当前位置 = s.dequeue();
if (当前位置 == 目标景点) break;
for (每一个相邻于当前位置的景点 Vertex v){
if (!v.visited){
v.parent = 当前位置;
// 不是规定，不过可以节省一点时间
if (v == 目标景点){
current = v;
break;
}
s.enqueue(Vertex v);
v.visited = true;
}
}
}

Stack <Vertex> solution = new Stack <Vertex>();
Vertex parent = current;
while (parent != 起始景点){
solution.push(parent);
parent = current.parent;
}

for (graph中的每一个vertex) vertex.visited = false;

return solution(); // 其实这里建议用一个 Path 的inner class 来装所获得的路线
}

然后再 main 求每两个景点之间的距离即可
public static void main(String[] argv){
PathFinder pf = new PathFinder();

Stack[][] 路径 = new Stack[10][10];

for(int i=0; i<pf.vertices.length; i++){
for(int j=i+1; j<pf.vertices.length; j++){
Stack s = pf.findPath(pf.vertices[i], pf.vertices[j]);
路径[i][j] = s; 路径[j][i] = s; // 假设你的graph是一个undirected graph

}

}

// 这么一来就大功告成了！对于每两个景点n 与 m之间的最短路径就是在 stack[n][m] 中

}

还有一种方法就是用Depth First Search递归式的寻找路径，不过这样比较慢，而且我的代码可能会造成stack overflow

public Stack dfs(Vertex 当前景点，Vertex 目标景点){
if(当前景点 == 目标景点) return;

Stack solution = new Stack();
Stack temp;
for (相邻于点钱景点的每一个 Vertex v){
if (!v.visited){
v.visited = true;
temp = dfs(v, 目标景点);
// 抱歉，不记得是stack.size()还是stack.length()

if (solution.size() == 0) solution = temp;
else if(temp.size() < solution.size()) solution = temp;

v.visited = false; 复原

}

}

return solution;

}
然后再在上述的Main中叫dfs...

参考：
http://www.cs.berkeley.e/~jrs/61b/lec/29
http://www.cs.berkeley.e/~jrs/61b/lec/28

8. 一批货物准备从A地到E地，有如下可能的路线提供选择：（最短路径问题），求算法设计，用java或者C语言

//定义结构节点
struct Node
{
std::string Name; //编号
std::list<Node*> Branch;//从该点可走的分支
}
//逻辑流程
1，初始化所有节点数据，定义开始和结束的点
2，从开始节点开始生成移动的树
3，第一次出现终点的层数就是最短路径长度

细节自己琢磨一下咯

9. 求java实现矩阵图上任意两点的最短路径源码

我用的是递归调用方法，有个小问题就是在打印步数的时候是返向的，原因是就是程序不断的调用自己，到最后判断基值位准退出调用。这才开始从栈里取出方法进行执行的原因。

代码欣赏：

publicstaticintstep=1;

=newStringBuffer();

publicstaticint[][]maze={{1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,1,0,0,0,0,0,1},

{1,0,1,0,0,0,1,0,1,1,1},

{1,0,0,0,1,0,1,0,0,0,1},

{1,0,1,1,0,0,1,0,0,1,1},//0代表可以通过，1代表不可通过

{1,0,1,0,1,1,0,1,0,0,1},

{1,0,0,0,0,0,0,0,1,0,1},

{1,0,1,0,1,0,1,0,1,0,1},

{1,0,0,1,0,0,1,0,1,0,1},

{1,1,1,1,1,1,1,1,1,1,1}};

publicstaticvoidmain(String[]args){

inti,j;//循环记数变量

Sample.way(1,1);//二维数组起始值从下标1，1开始

System.out.println("起点从坐标x=1,y=1开始");

System.out.println("终点坐标是x=8,y=9结束");

System.out.println("这是迷宫图表");

System.out.println("012345678910");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

for(i=0;i<10;i++){

System.out.print(""+i+"‖");

for(j=0;j<11;j++)

System.out.print("-"+maze[i][j]+"-‖");

System.out.println("");

System.out.println("+---+---+---+---+---+---+---+---+---+---+---+---+---+");

}

//打印显示步数

System.out.print(printStep.toString());

}

publicstaticbooleanway(intx,inty){

if(maze[8][9]==2)//代表递归终止条件（也就是当走出出口时标记为2）

returntrue;

else{

if(maze[y][x]==0){

maze[y][x]=2;

*下面if判断条件代表当前坐标为基点，

*根据判断对当前位置进行递归调用：如：

*往上、往右上、往右、往右下、往下、

*往左下、往左、往左上的坐标是否可走，

*判断是否可走的返回条件是：

*2代表可通过、1代表不能通过、3表示已经走过，但是未能走通。

if(way(x,y-1)){