问题描述
你好，
我有一个球员图.每个玩家有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
推荐答案
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中目标的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！