Click here to Skip to main content
12,406,795 members (55,846 online)
Rate this:
 
Please Sign up or sign in to vote.
See more: Java Algorithms
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) 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
Comments
Sandeep Mewara 24-Apr-12 5:14am
   
Sounds like a homework!

Tried anything? Any effort?
Rate this: bad
 
good
Please Sign up or sign in to vote.

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 Smile | :)
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 Smile | :)
Please check this info and google for an example code

Breadth-first search
  Permalink  
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.
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: bad
 
good
Please Sign up or sign in to vote.

Solution 2

You are lucky I'm bored. Smile | :)

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>();
        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));
        }
    }
}
  Permalink  
v2
Comments
erez_l 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)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Mobile
Web02 | 2.8.160730.1 | Last Updated 25 Apr 2012
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100