CODEWITHSUNDEEP
javasearchgraph
user3421241
user3421241

Reputation: 57

Create a graph so that I can apply Uniform Cost Search on it

Hello I'm trying to find the shortest path between 2 cities and I need to use UCS algorithm. I'm having troubles implementing the graph, I don't know if I did it correct. So far I have:

public class City {
    final private String id;  

      public City(String id) {
        this.id = id;
      }
      public String getId() {
        return id;
      }

      @Override
      public String toString() {
        return id;
      }  
}




public class Route {

private final City node;
private final int cost; 

  public Route(City node, int cost) {
    this.node = node;
    this.cost = cost;
  }

  public City getCity() {
    return node;
  }
  public int getCost() {
    return cost;
  }

  @Override
  public String toString() {
      return "{" + node + ", " + cost + "}";
  }

}

Upvotes: 0

Views: 486

Answers (1)

Liam M
Liam M

Reputation: 5432

This sounds like a homework question, so I'm not going to flat out tell you how to solve this one. Instead, let me suggest a way of looking at the problem that may allow you to find the answer on your own.

Take a step back and examine the algorithm. Ask yourself these questions:

  1. What concepts do I need to represent?
  2. What operations do I need to perform on these representations?
  3. What data structures and programming constructs support my needs?

You've identified cities (vertices), the routes between those cities (edges), and the entire map (graph), as the concepts you need to represent. So far, so good.

Next, examine the algorithm and determine what you need your representations (classes) to do and what you need to do with them. The need you're stuck on is simple: you need to be able to determine the cities that are immediately connected to a given city by a road. Look at your code and ask yourself:

  1. Have I organised my data in a way that supports my needs?
  2. What algorithm can I use to determine which cities are connected by a route?

Once you've answered these questions, ask yourself a 3rd question: is there a better way to meet this need? Can I change my data structures and/or my algorithm to solve this problem in a better way? If the answer is yes, go back to question 1 and 2. This list may provide you with a few ideas.

I think you should get a pencil and paper and draw the problem out. It's my experience that this is a good way to approach new problems and gain the understanding I require to come up with a program that can provide the solution.

Upvotes: 1

Related Questions