Click here to Skip to main content
15,867,308 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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):

Java
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) 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
Comments
Sandeep Mewara 24-Apr-12 5:14am    
Sounds like a homework!

Tried anything? Any effort?

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
 
Share this answer
 
Comments
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.
user_code 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.
user_code 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
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.


Java
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.

Java
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));
        }
    }
}
 
Share this answer
 
v2
Comments
user_code 24-Apr-12 8:31am    
Thanks a lot for your long and well explained solution :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900