到达Java中目标的最短路径 [英] shortest path to a destination in java
问题描述
你好，
我有一个球员图.每个玩家有2个邻居，并且图中有圆圈.每个边缘的长度不同(每个边缘的权重不同).
每个玩家都是Player类的对象.
我必须在类Player中编写一个称为Route的Java方法，该方法获取目标播放器，并且必须找到到达该目标的最短路径.
我列出了要保留的路径.
为了找到任何路径，我考虑了类似这样的算法(伪代码):
Hello,
I have a Graph of players. Each player has 2 neighbours, and there are circles in the graph. Each edge is of a different length (different weight for each edge).
Each player is an object of class Player.
I have to write a Java method called Route in class Player, that gets a destination player, and must find the shortest path to this destination.
I made a List to keep the founded path.
To find any path, I thought about an algorithm like this (pseudo code):
routeList.clear();
for (p : all players)
p.visited = false; // I put a visited member because the Graph has circles
// and We don't want infinite loops
...
List<Player> Route(Player destination)
{
List<Player> tempList = new List<Player>;
tempList.clear();
if (destination player)
{
tempList.addfirst(this);
routeList.add(this);
return tempList;
}
if (!isVisited())
{
this.visited = true;
for (p : GetNeighbours) // 2 neighbours for each player
{
tempList.addall(p.Route(destination));
if (!tempList.empty())
{
routeList.addfirst(p);
return tempList;
}
}
return tempList; // here it's an empty list
}
1)对于任何路径，此算法对我而言均无法正常工作.怎么了?
2)您能否帮助我进行更改，并开发一个返回最短路径的java方法?
谢谢
1) This algorithm for any path does not work properly for me. What is wrong?
2) Can you please help me with changing it and develop a java method that returns the SHORTEST path?
Thanks
推荐答案
您好，您尝试编写的东西看起来像DFS(深度优先搜索)
深度优先搜索
但是要完成此操作，您需要使用Recursion，这意味着Route函数必须调用自己.您几乎做到了:)
这里的问题是算法本身不是您所需要的
DFS会找到一条路径，但是您无法确定它是否正确，直到找到其他路径为止.没必要，因为您还有其他好的算法
就像您看到的一样，您需要找到起始节点和某些给定节点之间的最短路径
您应该使用BFS(宽度优先搜索).我想帮助您编写它，但是Java不是我的语言:)
请检查此信息，并向Google索取示例代码
广度优先搜索
Hello the thing you are trying to write really looks like a DFS(Depth-first search)
Depth-first search
but to complete it you need to use Recursion meaning that the function Route has to call herself. You almost did it :)
The problem here is that the algorithm itself isn''t what you need
DFS finds a path but you cant be sure if its the right one until you find the others. Which isn''t necessary because you have other good algorithms
Like you see it you need to find the shortest path between the start node and some given node
You should use BFS(Breadth-first search). I would like to help you write it but Java isnt my language :)
Please check this info and google for an example code
Breadth-first search
您很幸运，我很无聊. :)
我们将从设置开始；首先，您需要播放器和节点.您不能简单地引用其他玩家，因为noe还具有一个属性-length.
我在这里错过了很多代码，但是请确保节点两侧的两个播放器始终在其集合中包含该节点.
You are lucky I''m bored. :)
We''ll start with the set up; first of all you''ll need the player and nodes. You can''t have a simple reference to another player as the noe also has an attribute - length.
I have missed a lot of code here, but make sure that the two players on either side of the node always have the node in their collection.
class Player {
// player code
private List<node> connections;
List<node> getConnections() {
return this.connections;
}
}
class Node {
// a node connects two players and also has a length;
private Player from;
private Player to;
private int length;
Player getNext (Player from) {
if (from.equals(this.from)) {
return this.to;
} else if (from.equals(this.to)) {
return this.from;
}
return null;
}
}
接下来是要使用单独的类来计算路线.我喜欢这种方法，因为它可以将详细信息从Player类中抽象出来.
该算法相当简单:
0.从第一个记录开始，行进的距离.
1.对于当前节点中的每个节点:
2.如果是新的，请将其添加到列表中，或者
3.如果行进的长度短于当前距离，请更新路线.
遍历所有对象之后，最后的最短路径是到"玩家的当前距离实例.
Next up is to have a seperate class for calculating the route. I like this approach as it abstracts this detailed point away from the Player class.
The algorithm is reasonably simple:
0. Starting from the first record the distance travelled.
1. For each node from the current node:
2. If it is a new add it to the list, or
3. If the length travelled is shorter then current distance, update the route.
After the noes have all been traversed, the final shortest route is in the current distance instance for the ''to'' Player.
class Route {
private List<node> nodes;
private int length;
void buildRoute (Player from, Player to) {
// Starting at 'from' find the shortest routes to each player
ArrayList<distance> distances = new ArrayList<distance>();
distances.add(new Distance(from));
int pos = 0;
while (pos < distances.size()) {
Distance current = distances.get(pos);
for (Node node : current.getConnections() {
int length = current.length + node.getLength();
Player dest = node.getNext(current);
Distance next = null;
for (Distance d : distances) {
if (d.player.equals(dest)) {
next = d;
break;
}
}
if (next == null) {
next = new Distance(dest);
next.length = length+1; // this will now be updated below
distances.add(next);
}
if (length < next.length) {
next.nodes = current.nodes.clone();
next.nodes.add(node);
next.length = length;
}
}
pos++;
}
// find the final destinatiogn and take the route:
for (Distance d : distances) {
if (d.player.equals(to)) {
this.nodes = d.nodes;
this.length = d.length;
break;
}
}
}
class Distance {
Player player;
ArrayList<nodes> nodes;
int length;
Distance (Player player) {
this.player = player;
this.length = 0;
this.nodes = new ArrayList<nodes>();
}
public boolean equals(Object o) {
// shortend version
return (this.player.equals((Distance)o.player));
}
}
}
这篇关于到达Java中目标的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
