The cost of the cheapest routes between cities

[cubano007]

Hello everyone,
I have to make a program in Java. The task is:

I need to make a breakdown of the cost of the cheapest routes between individual cities. A route is a sequence of individual train or bus connections.

Out of N cities, M pairs of these cities are connected by railway lines. The legs between those cities do not cross anywhere except cities, because they may have bridges/tunnels. The cost of travelling between two cities directly connected by a railway line is A.

In addition to train connections, direct bus connections are possible, but between such pairs of cities for which: there is no direct railway connection AND, at the same time, the cheapest train connection requires one change. The cost of a bus ticket for one connection is B.

Input - the first line of the standard input contains the integers: N, M, K, A, B (1=<K<=N, 1<=A, B<= 100), where: N - number of cities, M - number of railway connections, K - the number of the starting city for which you need to generate a statement describing the cheapest routes, A - the cost of a ticket for one railway connection; B - the cost of a ticket for one bus connection.

Each of the following M lines contains two integers U and V (1<=U, V<=N, U ≠ V, for i=1,..,M) separated by a single space = these are the numbers of cities connected directly by railway track sections. Assumption: from city number K, you can travel by train to all other cities.

Output - the program writes N lines to the standard output. The line i (i=1,2,..,n) contains an integer. The cost of the cheapest route from city number K to city number i. Out of these lines, the line number k should contain the number 0.

Assumption: all train and bus connections are bi-directional.

In "Main" class I declared integers: n, m, k, a, b. Besides that, I did constructors, getters, setters and declarations of other variables in class "City" as you can see.

import java.util.ArrayList;
import java.util.List;

public class City {

    public City() {}

    public City (int cityIndex) {
    this.cityIndex = cityIndex;}

    private int cityIndex;
    private int busPrice;
    private int trainPrice;
    private int transferCounter;

    private ArrayList<Integer> connections = new ArrayList<>();

    public int getCityIndex() {
    return cityIndex;}

    public void setCityIndex(int cityIndex) {
    this.cityIndex = cityIndex;
}

public int getTrainPrice() {
return trainPrice;
}

public void setTrainPrice(int trainPrice) {
    this.trainPrice = trainPrice;
}

public int getBusPrice() {return busPrice;}

public void setBusPrice(int busPrice) {
    this.busPrice = busPrice;
}

public int getTransferCounter() {
return transferCounter; }

public void setTransferCounter (int transferCounter)
{this.transferCounter = transferCounter;}

public ArrayList<Integer> getConnections() {
return connections;
    }
}

Thank you in advance for your help.

 

[WhiteCube]

This can be solved using Dijkstra's shortest path algorithm.

Convert the U V pairs in the standard input, into an adjacency matrix (a vertex is a city, an edge is a train or bus connection). Replace every 1 with the value of A.

For every city, use Dijkstra to compute the shortest paths.

That will yield enough information to determine where the bus connections are. Place the value of B on those edges.

The matrix now contains, A values, B values, and zeroes. For city K, use Dijkstra to compute the shortest paths.

 

[thugbunny]

To complete the task you described, you will need to implement a method that calculates the cheapest route from the starting city to each of the other cities. You can do this by using a graph traversal algorithm such as Dijkstra's or breadth-first search.

 

[Bloom18]

The next step is to create a method that will calculate the cheapest route from city number K to all other cities.