CODEWITHSUNDEEP
javasearchgraphtreeshortest-path
user2587878
user2587878

Reputation: 131

Uniform-Cost search

I am having difficulty wrapping my head around how to approach this problem. I have a .txt file that contains 2 cities and the distance between them space delimited on each line. My goal is to take 2 cities as args, and find the shortest path. I have created 3 classes. Main, Node, and Road(edges).

public class Node {
    public Node parent;
    public final String cityName;
    public double pathCost;
    public Road[] neighbors;

    public Node(String x){
        cityName = x;
    }

    public String myCity(){
        return cityName;
    }
}

and

public class Road {
    public final double distance;
    public final Node destination;

    public Road(Node x, double cost){
        distance = cost;
        destination = x;
    }
}

I am wondering how to store the nodes and edges. The following code is my attempt. It seems to work, but I feel like it is not very efficient.

public void initNodes(){
    ArrayList<String> cities = new ArrayList<String>();
    for(String line : myLines){
        String[] split = line.split("\\s+");
        if(!cities.contains(split[0]))
        {
            cities.add(split[0]);
            Node n1 = new Node(split[0]);
            myNodes.add(n1);
        }
        if(!cities.contains(split[1]))
        {
            cities.add(split[1]);
            Node n = new Node(split[1]);
            myNodes.add(n);
        }
    }       
}

after first calling that method to create a Node for each city, I call the following method to create the Roads.

public void initRoads(){
    for(Node n:myNodes){
        for(String line : myLines){
            String[] split = line.split("\\s+");
            if(split[0].equals(n.cityName)){
                for(Node n2:myNodes){
                    if(split[1].equals(n2.cityName)){
                        Road r1 = new Road(n2,Integer.parseInt(split[2]));
                        Road r2 = new Road(n,Integer.parseInt(split[2]));
                        n.neighbors.add(r1);
                        n2.neighbors.add(r2);
                    }
                }
            }
        }
    }
}

With all the nested for loops, it seems that this would be impossible as the number of cities and edges grow. Is there a way to solve this problem without creating the graph like this? Is there an easier way to create the graph? Thanks for any help.

Upvotes: 1

Views: 872

Answers (1)

shapiro yaacov
shapiro yaacov

Reputation: 2346

Form a glance, there are a few points I think can be improved here:

  1. You are referring to each road as if it has a destination. You did not specifically say that the roads are one-way roads, so it makes sense to make a road a two way road.

  2. You are looping through the file twice - why? When you have read a line, after adding the two cities (or finding them in the Dictionary), add the road.

  3. Use a Dictionary for the cities, not lists. This way you can find cities faster, and skip the first (and second) loop in initRoads().

  4. I would also think of roads as a class with an ID, two cities, and distance. If you want, each city can hold a list of roads that are connected to it.

I am not native to Java, but the general idea should be something like this:

    public class Node {
        public Node parent;
        public final String cityName;
        public double pathCost;
        public int[] roads;

        public Node(String x){
            cityName = x;
        }

        public String myCity(){
            return cityName;
        }
    }

    public class Road {
        public final int ID;
        public final double distance;

        public Road(int id, double cost){
            ID = id;
            distance = cost;
        }
    }

    public Dictionary<String> cities = new Dictionary<String>();

    public void initNodes(){
        int curID = 0;
        Node first, second;
        for(String line : myLines){
            String[] split = line.split("\\s+");
            first = getNode(split[0]);
            second = getNode(split[1]);

            Road r1 = new Road(curID,split[2]);
            first.roads.add(curID);
            second.roads.add(curID);
            curID++;        
        }       
    }

    // Like a singleton...
    public void getNode(string cityName){

        if(!cities.contains(cityName))
        {
            Node newCity = new Node(cityName);
            cities.add(cityName, newCity);
        }
        return cities.get(cityName);    
    }

Upvotes: 1

Related Questions