Distance between cities

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

53 Replies - 32037 Views - Last Post: 15 May 2010 - 07:01 PM Rate Topic: -----

#1 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Distance between cities

Posted 12 May 2010 - 01:28 PM

I have a project that should prompt the user to enter as many cities as he likes with x and y coordinates. When he is done entering cities the program should use recursion to pick each city from the list and calculate the distance. So lets say the user enters 3 cities.

New York 10, 15
Las Vegas 33, 55
Denver 22, 44

I need to calculate the distance from New York to Las Vegas and from Las Vegas to Denver, then add it all up and display it.

Here are the actual instructions: Create a Java program that prompts the user for a list of cities, where each city has a name and x and y coordinates. After all cities have been entered, the program should use a recursive algorithm to print the length of all possible routes that start at the first city entered and end at the last city entered, and visit every city in the list. For each route, the program should print the name of each city visited, followed by the length of the route.

Can anyone point me in the right direction? If you have any suggestions on how to solve this a different way please let me know.
Here is what I have so far:

package Citydistance;

import java.util.*;


public class Cityroute {

public static void main(String[] args)
          {
                 Scanner scanner = new Scanner (System.in);
                 LinkedList citiesList = new LinkedList();
                 LinkedList yList = new LinkedList();
                 LinkedList xList = new LinkedList();

                 String city = "";
                 double x = 0;
                 double y = 0;
                 int choice = 0;

                  // First run to enter the starting location.
                 System.out.println("Enter the name of the city:");
                 city = scanner.next();
                 citiesList.addFirst(city);
                 System.out.println("Enter the X coordinate");
                 x = scanner.nextDouble();
                 xList.addFirst(x);
                 System.out.println("Enter the Y coordinate");
                 y = scanner.nextDouble();
                 yList.addFirst(y);

                 System.out.println("City: " + city + " X " + x + " Y " + y);
                 System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

                 System.out.println();
                 System.out.println("Pick one of the following choices:");
                 System.out.println(" 1. Enter another city");
                 System.out.println(" 2. Enter destination");
                 System.out.println(" 3. Exit");

                 System.out.println();
                 choice = scanner.nextInt();

                 
                 while(choice == 1)
                 {
                        switch(choice)
                        {
                           // enter additional cities
                           case 1:
                                  System.out.println("Enter the name of the city:");
                                  city = scanner.next();
                                  citiesList.add(city);
                                  System.out.println("Enter the X coordinate");
                                  x = scanner.nextDouble();
                                  xList.add(x);
                                  System.out.println("Enter the Y coordinate");
                                  y = scanner.nextDouble();
                                  yList.add(y);

                                  System.out.println("City: " + city + " X " + x + " Y " + y);
                                  System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

                                                // ask for next choice
                                  System.out.println();
                                  System.out.println("Pick one of the following choices:");
                                  System.out.println(" 1. Enter another city");
                                  System.out.println(" 2. Enter destination");
                                  System.out.println(" 3. Exit");

                                  System.out.println();
                                  choice = scanner.nextInt();

                                  break;

                           case 3:
                                        // Exit
                                  System.out.println("Good bye");
                                  System.exit(0);
                                  break;

                        }// end switch
                 }// end loop

                        // Enter final destination
                 System.out.println("Enter your final destination:");
                 city = scanner.next();
                 citiesList.addLast(city);
                 System.out.println("Enter the X coordinate");
                 x = scanner.nextDouble();
                 xList.addLast(x);
                 System.out.println("Enter the Y coordinate");
                 y = scanner.nextDouble();
                 yList.addLast(y);

                 System.out.println("City: " + city + " X " + x + " Y " + y);
                 System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);


                 // Compute the distance between all the cities recursively, print all cities, and the total distance
                 // between all cities. Not Sure How....?????

                 double distance = 0;
                 double endX = 0;
                 double startX = 0;
                 double endY = 0;
                 double startY = 0;
                 distance = Math.sqrt((endX-startX)*(endX-startX) + (endY-startY)*(endY-startY));

          }// end main
   }//end class



Is This A Good Question/Topic? 0
  • +

Replies To: Distance between cities

#2 japanir   User is offline

  • jaVanir
  • member icon

Reputation: 1014
  • View blog
  • Posts: 3,025
  • Joined: 20-August 09

Re: Distance between cities

Posted 12 May 2010 - 02:25 PM

first, don't do it in the main.
declare a new method that accepts a List of distances as parameter.
now, do you know what is recursion? did you try implementing something? written any code?
If not, i first suggest that you read some tutorials about recursion, then try implement something in code.
If you have specific problems,feel free to post again with the code you have written, and we would love to help.
recursion in java:
http://danzig.jct.ac.../recursion.html
Was This Post Helpful? 0
  • +
  • -

#3 divinespirit9671   User is offline

  • New D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 30
  • Joined: 01-May 10

Re: Distance between cities

Posted 12 May 2010 - 02:40 PM

I suggest you read about Floyd-Warshall algorithm.This algorithm finds shortest path between all pairs of vertices in a graph.I think you can apply similar logic to cities.
Refer following link for more info about Floyd-warshall algorithm
Floyd Warshall algorithm




If you feel I was helpful,please press THANKS button

This post has been edited by divinespirit9671: 12 May 2010 - 02:41 PM

Was This Post Helpful? 1
  • +
  • -

#4 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12656
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Distance between cities

Posted 12 May 2010 - 03:12 PM

@JynxRD: This sounds exactly like Dijkstra's algorithm for the shortest path between two points on a Graph algorithm. Of course, you can adapt it to cover all paths as well.

@divinespirit9671: That would be a good algorithm if the OP was comparing distances between two points only, rather than traversing the Graph.
Was This Post Helpful? 1
  • +
  • -

#5 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Re: Distance between cities

Posted 12 May 2010 - 03:33 PM

Yea that's a bit above my understanding right now. It has to find all routes as well so one route would be City 1 to City 3 to City 2 to City 4 and another would be City 1 to City 2 to City 3 to City 4.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12656
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Distance between cities

Posted 12 May 2010 - 05:26 PM

Basically, Dijkstra's algorithm finds the shortest possible routes from point A to all points, not just point B. Really, you will need to use some fairly advanced Graph Theory algorithms, like Dijkstra's, to accomplish this task. You should probably first start by designing a City class, with attributes name, x, and y. Then weight your Graph according to distance from previous Vertices.

Just a note that the parallel array model is very poor design, due to a lack of encapsulation. Parallel dynamic collections, like LinkedLists, are even worse design b/c it is very easy to corrupt data via mismatching. Also, LinkedLists (and every other Java Collection for that matter) is Generic as of Java 1.5, and should therefore be declared with the Generic type (ie., LinkedList<String>) to avoid deprecation warnings.
LinkedList citiesList = new LinkedList(); 
LinkedList yList = new LinkedList(); 
LinkedList xList = new LinkedList();



You may also want to check out my tutorials on class design Moving Away From Parallel Arrays, and my tutorial on implementing a generic Graph structure.
Was This Post Helpful? 0
  • +
  • -

#7 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Re: Distance between cities

Posted 12 May 2010 - 05:50 PM

Once I can get what I have functioning then maybe I can change some things. I need to understand what I have and whats wrong first.

Am I any closer here? I been working on this for the past 5 hours. I know, I'm a newb.

package Citydistance;

/**
 *
 * @author Ryan
 */

 import java.util.*;


public class Cityroute {

    /**
     * @param args the command line arguments
     */
public static void main(String[] args)
          {
                 Scanner scanner = new Scanner (System.in);
                 LinkedList citiesList = new LinkedList();
                 LinkedList yList = new LinkedList();
                 LinkedList xList = new LinkedList();

                 String city = "";
                 double x = 0;
                 double y = 0;
                 int choice = 0;

                  // First run to enter the starting location.
                 System.out.println("Enter the name of the city:");
                 city = scanner.next();
                 citiesList.addFirst(city);
                 System.out.println("Enter the X coordinate");
                 x = scanner.nextDouble();
                 xList.addFirst(x);
                 System.out.println("Enter the Y coordinate");
                 y = scanner.nextDouble();
                 yList.addFirst(y);

                 System.out.println("City: " + city + " X " + x + " Y " + y);
                 System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

                 System.out.println();
                 System.out.println("Pick one of the following choices:");
                 System.out.println(" 1. Enter another city");
                 System.out.println(" 2. Enter destination");
                 System.out.println(" 3. Exit");

                 System.out.println();
                 choice = scanner.nextInt();

                 boolean isDone = false;
                 while(!isDone) {

                 System.out.println("Pick one of the following choices:");
                 System.out.println(" 1. Enter another city");
                 System.out.println(" 2. Enter destination");
                 System.out.println(" 3. Exit");
                 choice = scanner.nextInt();

                 switch(choice) {
                 case 1:
                 //get new city
                 break;
                 case 2:
                 //get destination city
                 isDone = true;
                 break;
                 case 3:
                 System.exit(1);
                 default: break; //input mismatch
                 }
                 if(isDone)break;
                 }

            

                 // Enter final destination
                 System.out.println("Enter your final destination:");
                 city = scanner.next();
                 citiesList.addLast(city);
                 System.out.println("Enter the X coordinate");
                 x = scanner.nextDouble();
                 xList.addLast(x);
                 System.out.println("Enter the Y coordinate");
                 y = scanner.nextDouble();
                 yList.addLast(y);

                 System.out.println("City: " + city + " X " + x + " Y " + y);
                 System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);


                 // Compute the distance between all the cities recursively, print all cities, and the total distance
                        // between all cities. Not Sure How....?????

          class computeDist {

          double dist(double distance, double endX, double startX, double endY, double startY) {
          double result;
          result = Math.sqrt((endX-startX)*(endX-startX) + (endY-startY)*(endY-startY));
          return result;

     }

}
          class Recursion {
          computeDist f =new computeDist();
          System.out.println(“Distance of city is “ + f.dist(city));

     }

}

          }// end main
   //end class


Was This Post Helpful? -1
  • +
  • -

#8 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12656
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Distance between cities

Posted 12 May 2010 - 05:57 PM

First, I believe I just explained about why parallel Linked Lists are bad, as well as provided a tutorial. In addition, you should be using Generic Linked Lists. So if you want your List to store Strings, then declare a LinkedList<String>.

So basically, are you working on generating permutations? So if you have 5 cities, and you need to go from Cities 1-5, would you basically have something like:

Quote

12345
12435
13245
13425
14235
14325

Was This Post Helpful? 0
  • +
  • -

#9 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Re: Distance between cities

Posted 12 May 2010 - 06:33 PM

View Postmacosxnerd101, on 12 May 2010 - 04:57 PM, said:

First, I believe I just explained about why parallel Linked Lists are bad, as well as provided a tutorial. In addition, you should be using Generic Linked Lists. So if you want your List to store Strings, then declare a LinkedList<String>.

So basically, are you working on generating permutations? So if you have 5 cities, and you need to go from Cities 1-5, would you basically have something like:

Quote

12345
12435
13245
13425
14235
14325


From my understanding yes. It also tells me that I need to use the following attached calculation.

See image. (Looks black but shows when I click it.)

Attached image(s)

  • Attached Image

This post has been edited by JynxRD: 12 May 2010 - 06:33 PM

Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12656
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Distance between cities

Posted 12 May 2010 - 06:35 PM

That's how you calculate distance between two (x,y) coordinates.

As for the cities, you may want to take a look at permutation algorithms (we have a bunch of permutation snippets in the Java snippets section). Basically, you'll want to put the start and end cities on each end, and the results of each permutation for the remaining cities in the middle, like I showed.
Was This Post Helpful? 0
  • +
  • -

#11 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Re: Distance between cities

Posted 12 May 2010 - 06:53 PM

So I need to add something like this. But I don't know how to make it work with this.

package Citydistance;

/**
 *
 * @author Ryan
 */

 import java.util.*;


public class Cityroute {

    /**
     * @param args the command line arguments
     */
public static void main(String[] args)
          {
                 Scanner scanner = new Scanner (System.in);
                 LinkedList citiesList = new LinkedList();
                 LinkedList yList = new LinkedList();
                 LinkedList xList = new LinkedList();

                 String city = "";
                 double x = 0;
                 double y = 0;
                 int choice = 0;

                  // First run to enter the starting location.
                 System.out.println("Enter the name of the city:");
                 city = scanner.next();
                 citiesList.addFirst(city);
                 System.out.println("Enter the X coordinate");
                 x = scanner.nextDouble();
                 xList.addFirst(x);
                 System.out.println("Enter the Y coordinate");
                 y = scanner.nextDouble();
                 yList.addFirst(y);

                 System.out.println("City: " + city + " X " + x + " Y " + y);
                 System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);

                 System.out.println();
                 System.out.println("Pick one of the following choices:");
                 System.out.println(" 1. Enter another city");
                 System.out.println(" 2. Enter destination");
                 System.out.println(" 3. Exit");

                 System.out.println();
                 choice = scanner.nextInt();

                 boolean isDone = false;
                 while(!isDone) {

                 System.out.println("Pick one of the following choices:");
                 System.out.println(" 1. Enter another city");
                 System.out.println(" 2. Enter destination");
                 System.out.println(" 3. Exit");
                 choice = scanner.nextInt();

                 switch(choice) {
                 case 1:
                 //get new city
                 break;
                 case 2:
                 //get destination city
                 isDone = true;
                 break;
                 case 3:
                 System.exit(1);
                 default: break; //input mismatch
                 }
                 if(isDone)break;
                 }

            

                 // Enter final destination
                 System.out.println("Enter your final destination:");
                 city = scanner.next();
                 citiesList.addLast(city);
                 System.out.println("Enter the X coordinate");
                 x = scanner.nextDouble();
                 xList.addLast(x);
                 System.out.println("Enter the Y coordinate");
                 y = scanner.nextDouble();
                 yList.addLast(y);

                 System.out.println("City: " + city + " X " + x + " Y " + y);
                 System.out.println("CityList: " + citiesList + " X " + xList + " Y " + yList);


                 // Compute the distance between all the cities recursively, print all cities, and the total distance
                        // between all cities. Not Sure How....?????

          class computeDist {

          double dist(double distance, double endX, double startX, double endY, double startY) {
          double result;
          result = Math.sqrt((endX-startX)*(endX-startX) + (endY-startY)*(endY-startY));
          return result;

     }

}
class Permute {

       

        public void swap(char[] set, double x, double y) //java doesn't allow the same pass by reference like C++

        {
                char ch = set[second]; //so we pass the char array and assign, since this will hold
                set[second] = set[first]; //swap the values
                set[first] = ch;
        }
        public int permute(char[] set, int begin, int end)
        {
                int i;
                int range = end - begin;
                if (range == 1) {
                        System.out.println(set); //print out each permutation
                } else {
                        for(i=0; i<range; i++) {
                                swap(set, begin, begin+i);                //initial swap
                                permute(set, begin+1, end);                //recursion
                                swap(set, begin, begin+i);       //swap back
                        }
                }
                return 0;
        }
 

        //***************TEST EXAMPLE********************

        public void main(String[] args) {
                char[] test = {'a','b','c','d'};;
                permute(test, 0, 4);
        }
     }
}
          }// end main
   //end class


Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12656
  • View blog
  • Posts: 45,830
  • Joined: 27-December 08

Re: Distance between cities

Posted 12 May 2010 - 07:01 PM

Why do you insist on using parallel Linked Lists and without Generics? Parallel Linked Lists is very bad practice, and Linked Lists without Generics are deprecated. Did you look at my tutorial on Moving Away From Parallel Arrays?

Also, you will only want to permute the cities that are not the beginning and end points. Note that you will probably want to include a method for permutations inside your Cityroute class if you want to work via the main() method (note they should then be declared as static), or you will have to create an instance of the Permute class in main() to invoke the methods if you don't want them static. Also, you should only be working out of one main() method, as it is the starting point to run your programs.
Was This Post Helpful? 0
  • +
  • -

#13 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Re: Distance between cities

Posted 12 May 2010 - 07:26 PM

View Postmacosxnerd101, on 12 May 2010 - 06:01 PM, said:

Why do you insist on using parallel Linked Lists and without Generics? Parallel Linked Lists is very bad practice, and Linked Lists without Generics are deprecated. Did you look at my tutorial on Moving Away From Parallel Arrays?

Also, you will only want to permute the cities that are not the beginning and end points. Note that you will probably want to include a method for permutations inside your Cityroute class if you want to work via the main() method (note they should then be declared as static), or you will have to create an instance of the Permute class in main() to invoke the methods if you don't want them static. Also, you should only be working out of one main() method, as it is the starting point to run your programs.


I'll be honest with you, I don't change a lot of what you suggest because I simply don't know how. This is only my second project in this class so either they assume everyone is already good with Java or I'm just not grasping it.
Was This Post Helpful? 0
  • +
  • -

#14 JynxRD   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 78
  • Joined: 06-November 08

Re: Distance between cities

Posted 12 May 2010 - 08:49 PM

Is any of this better?

import java.io.*;
import java.util.*;

public class Cityroute
{

        public static void main(String[] args)
        {

                //Create Variables.
                List<String> cityName = new LinkedList<String>();
                List<Integer> cityX = new LinkedList<Integer>();
                List<Integer> cityY = new LinkedList<Integer>();

                //create a buffered reader to read input from the keyboard.
                BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

                //Initiate a try block to catch any errors for the streamreader object.
                try
                {

                        //Prompt the user for the city of orgin.
                        System.out.println("Please enter the city of orgin:");
                        String orginCity = in.readLine();
                        System.out.println("Please enter the X cordinate for the city of orgin:");
                        int orginX = Integer.parseInt(in.readLine());
                        System.out.println("Please enter the Y cordinate for the city of orgin:");
                        int orginY = Integer.parseInt(in.readLine());

                        //Prompt the user for the Destination city.
                        System.out.println("Please enter the destination city:");
                        String destinationCity = in.readLine();
                        System.out.println("Please enter the X cordinate for the destination city:");
                        int destinationX = Integer.parseInt(in.readLine());
                        System.out.println("Please enter the Y cordinate for the destination city:");
                        int destinationY = Integer.parseInt(in.readLine());

                        //Initilize a loop to prompt the user for one of more additional cities.
                        boolean cont = true;
                        while (cont == true)
                        {

                                //Prompt the user for the next city.
                                System.out.println("Please enter the next city(Type \"exit\" to quit.):");
                                String nextCity = in.readLine();
                                if (nextCity.equalsIgnoreCase("exit"))
                                {
                                        cont = false;
                                }
                                else
                                {
                                        System.out.println("Please enter the X cordinate for the next city:");
                                        int nextX = Integer.parseInt(in.readLine());
                                        System.out.println("Please enter the Y cordinate for the next city:");
                                        int nextY = Integer.parseInt(in.readLine());

                                        //Add the information entered to the appropriate stacks.
                                        cityName.add(nextCity);
                                        cityX.add(nextX);
                                        cityY.add(nextY);
                                }

                        }

                }

                //Catch block to complete try block.
                catch(IOException e)
                {
                        System.out.println(e.getMessage());
                }

                //Convert the linked lists to arrays.
                Object[] cityNameArray = cityName.toArray();
                Object[] cityXArray = cityX.toArray();
                Object[] cityYArray = cityY.toArray();

        }

        public void routes()
        {



        }

}


Was This Post Helpful? 0
  • +
  • -

#15 divinespirit9671   User is offline

  • New D.I.C Head
  • member icon

Reputation: 7
  • View blog
  • Posts: 30
  • Joined: 01-May 10

Re: Distance between cities

Posted 13 May 2010 - 12:05 AM

@macosxnerd101
Indeed you are right,Dijkstra's algorithm would be much better choice than floyd-warshall in this case.

@JynxRD
You can also try the foll. approach to solve your problem:-

1:-create separate class city which has instance variables x,y;
2:-Next instead of creating linked list,create a graph by linking objects of class city;
3:-You can use your formula of calculating distance to define the weight of edge between two adjacent cities.Cities are adjacent if we can go directly from one city to another;
4:-Now you can display path from you starting city to all other cities using dijkstra's algorithm


Hope it helps


If I was helpful ,please press THANKS button

This post has been edited by divinespirit9671: 13 May 2010 - 12:37 AM

Was This Post Helpful? 0
  • +
  • -

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »