12,406,795 members (55,846 online)
Rate this:
See more:
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)
{
return tempList;
}

if (!isVisited())
{
this.visited = true;
for (p : GetNeighbours)    // 2 neighbours for each player
{
if (!tempList.empty())
{
return tempList;
}
}

return tempList;     // here it's an empty list

}
```

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
Posted 23-Apr-12 22:03pm
Sandeep Mewara 24-Apr-12 5:14am

Sounds like a homework!

Tried anything? Any effort?

Rate this:

Solution 1

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

Nagy Vilmos 24-Apr-12 5:52am

Using recursion brings in the added problem of what has been visited. Using OP's approach, once a node is visited it will not re calculated if it is arrived at using a shorter route. The below will check all routes.
Argonia 24-Apr-12 6:26am

I don't think its a good idea to put the visited array in the class definition. If you don't put it there and use kind of indexing there will be no problem using recursion.
erez_l 24-Apr-12 8:31am

Thanks. How can I add a list for the path to a BFS algorithm?
Argonia 24-Apr-12 9:04am

I am not very good with Java but cant you make it public static ? Maybe you will need to declare a class for the array itself.
erez_l 24-Apr-12 9:17am

I mean, about the BFS algorithm (not java programming) - how do I build this list for BFS, when to add a node to the path, when to remove a node from the path, etc
Rate this:

Solution 2

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;
}
}```

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>();
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
}

if (length < next.length) {
next.nodes = current.nodes.clone();
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));
}
}
}
```
v2
erez_l 24-Apr-12 8:31am

Thanks a lot for your long and well explained solution :)

Top Experts
Last 24hrsThis month
 OriginalGriff 240 Karthik Bangalore 230 Richard MacCutchan 180 Afzaal Ahmad Zeeshan 75 ppolymorphe 40
 OriginalGriff 7,957 Karthik Bangalore 3,531 ppolymorphe 3,420 Richard MacCutchan 2,652 F-ES Sitecore 2,300