Shortest path and distance algorithm for Java?

Question

In the code below I am trying to calculate the distance between two cities. The user will enter a city name and a city, then the user will enter the distance between those cities, and finally enter the price to travel between those cities. I am not getting it to evaluate yet as I am unsure exactly how I am going to do this. My question is I am looking for pointers and suggestions on how one would do this.

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

public class CityCalcultor {

    static LinkedList<String> cities = new LinkedList<String>();
    static LinkedList<Integer> distance = new LinkedList<Integer>();
    static LinkedList<Integer> price = new LinkedList<Integer>();

    public static void main(String[] args) throws IOException {
        Scanner input = new Scanner(System.in);
        String text;
        int option = 0;
        while (true) {
            System.out.println("\nWhat would you like to do:\n"
                + "1. Add a city to the system\n"
                + "2. Add a path to the system\n"
                + "3. Evalute paths\n"
                + "4. Exit\n" + "Your option: ");
            text = input.nextLine();
            option = Integer.parseInt(text);

            switch (option) {
                case 1:
                    EnterCity();
                    break;
                case 2:
                    EnterPath();
                    break;
                case 3:
                    EvalutePaths();
                    break;
                case 4:
                    return;
                default:
                    System.out.println("ERROR INVALID INPUT");
            }
        }
    }

    public static void EnterCity() {
        String c = "";
        LinkedList<String> cities = new LinkedList<String>(Arrays.asList(c));
        Scanner City = new Scanner(System.in);
        System.out.println("Please enter the city name ");
        c = City.nextLine();
        cities.add(c);
        System.out.println("City " + c + " has been added ");
    }

    public static void EnterPath() {
        Scanner Path = new Scanner(System.in);
        int d = 0;
        int p = 0;
        System.out.println("Enter the starting city ");
        System.out.println();
        System.out.println(Path.nextLine());
        System.out.println("Enter the ending city ");
        System.out.println(Path.nextLine());
        System.out.println("Enter the distance between the two cities ");
        d = Path.nextInt();
        for (d = 0; d > 0; d++) {
            distance.add(d);
        }
        System.out.println("Enter the price between the two cities ");
        p = Path.nextInt();
        for (p = 0; p > 0; p++) {
            price.add(p);
        }
        System.out.println("The route was sucessfully added ");
    }

    private static void EvalutePaths() {
    }
}

Answer 1

There are two ways I can interpret your question: you either want to evaluate every possible path between pairs of cities (which is technically infinite, unless you restrict revisiting of cities), or you want to find the shortest distance/cheapest way to get from city to city.

I don't feel like trying to figure out the first one, and I'm pretty sure you mean the second, so I'm going with that.

The solution to the problem is to model your cities and the routes between them using a graph, where each vertex is a city, and each edge is a direct path between two cities. The edges are weighted either by the distance between the cities, or by the cost of travel.

You can then apply Dijkstra's Algorithm (or one of its variants) to find the path between any source vertex (city of departure) to all other vertices (destination cities) with the smallest total weight (i.e. smallest distance or lowest cost). If you apply this algorithm using each vertex in turn as the source, you will have built a complete model of the cheapest routes between any two cities.

Answer 2

The pretty much standard way of calculating shortest paths is A*