Finalizando Codigo

Bom dia, então galera estou fazendo um projeto de cadastro de cidades, no caso o usuário tem a opção de cadastrar a cidade, pesquisa-lá, pesquisar todas as cidades cadastradas e mostrar a melhor rota para chegar na ultima cidade cadastrada.
Minha duvida e na melhor rota eu preciso entender alguma forma em que pergunte para o usuário a cidade em que ele vai sair e a cidade em que ele quer chegar, a quantidade em KM gasta pelo usuário até chegar o destino, e as cidades que o usuário irá percorrer até chegar a cidade desejada.
O código que eu fiz está logo abaixo.

A CLASSE Estado:

public class Estado {
private String nCidade, prefeito;
private int nHabitantes;
private String vizinhos;

public Estado(){
    
}

public String getnCidade() {
    return nCidade;
}

public void setnCidade(String nCidade) {
    this.nCidade = nCidade;
}

public String getPrefeito() {
    return prefeito;
}

public void setPrefeito(String prefeito) {
    this.prefeito = prefeito;
}

public int getnHabitantes() {
    return nHabitantes;
}

public void setnHabitantes(int nHabitantes) {
    this.nHabitantes = nHabitantes;
}

public String getVizinhos() {
    return vizinhos;
}

public void setVizinhos(String vizinhos) {
    this.vizinhos = vizinhos;
}

public String toString() {
    String str  = toString() + "NOME CIDADE: " + getnCidade() 
            + "\nNUMERO DE HABITANTES: " + getnHabitantes()
            + "\nNOME PREFEITO: " + getPrefeito()
            + "\nCIDADES VIZINHAS: " + getVizinhos();
    return str;
}

}

A classe Principal que executa o programa:

public class Principal {
public static void main(String[] args){
String City, nCidade, nHabitantes, prefeito, vizinhos;
int x = 0, cont =1;
int y = 9;
ArrayList cd = new ArrayList <>();
String nomes = “”;
String cidadeBuscada = “NAO FOI ENCONTRADA”;
do {
City = JOptionPane.showInputDialog(null,"|ESCOLHA A OPÇÃO DESEJADA|"
+ “\n1) CADASTRAR CIDADE”
+ “\n2) MOSTRA CIDADES CADASTRADAS”
+ “\n3) PESQUISAR CIDADE”
+ “\n4) MELHOR ROTA”
+ “\n5) DIGITE ESC PARA SAIR”,"|ROTA FELIZ|", JOptionPane.PLAIN_MESSAGE);

	do {
	if(City.toUpperCase().equals("1")){
		Estado entidade = new Estado();
		nCidade = JOptionPane.showInputDialog(null,"NOME DA CIDADE: ","CADASTRO", JOptionPane.PLAIN_MESSAGE);
		entidade.setnCidade(nCidade);
		nHabitantes = JOptionPane.showInputDialog(null,"QUANTIDADE DE HABITANTES: ","CADASTRO", JOptionPane.PLAIN_MESSAGE);
		entidade.setnHabitantes(Integer.parseInt(nHabitantes));
		prefeito = JOptionPane.showInputDialog(null,"NOME DO PREFEITO: ","CADASTRO", JOptionPane.PLAIN_MESSAGE);
		entidade.setPrefeito(prefeito);
		vizinhos = JOptionPane.showInputDialog(null,"VIZINHOS: ","CADASTRO", JOptionPane.PLAIN_MESSAGE);
		entidade.setVizinhos(vizinhos);
		cd.add(entidade);
		x = Integer.parseInt(JOptionPane.showInputDialog(null,"DIGITE QUALQUER TECLA PARA SAIR DO PROGRAMA OU \n0 PARA CONTINUAR CADASTRANDO"));
	}cont++;
	}while ((x==0)&&(cont<=2));


    if(City.toUpperCase().equals("2")){
        
        for(Estado nome : cd){
		nomes += nome+"\n";
    }
    JOptionPane.showMessageDialog(null, nomes, "TODAS AS CIDADES", JOptionPane.INFORMATION_MESSAGE);
}
    
    
    
    if(City.toUpperCase().equals("3")){
        String busca = JOptionPane.showInputDialog(null,"DIGITE A CIDADE DESEJADA: ","PESQUISAR CIDADE", JOptionPane.PLAIN_MESSAGE);
            for (int i = 0; i < cd.size(); i++) {
                if(cd.get(i).getnCidade().equals(busca)) {
                cidadeBuscada = (
                cd.get(i).getnCidade()+ "\n" +
                cd.get(i).getnHabitantes()+ "\n" +
                cd.get(i).getPrefeito()+ "\n" +
                cd.get(i).getVizinhos()+ "\n");
                }

            JOptionPane.showMessageDialog(null, cidadeBuscada, "CIDADE PESQUISADA", JOptionPane.INFORMATION_MESSAGE);
            }
    }
    
        if(City.toUpperCase().equals("4")){
        
            
        }
            
            }while (y==9);

}

}

Poderia explicar melhor?
Não consegui entender o que se deve fazer.

Você pode criar um grafo onde os vértices representem as cidades e as arestas a distância entre elas.
Aí pode executar um algoritmo de Dijkstra em cima desse grafo para calcular o melhor caminho.

Imagino que seja pra isso que você está usando o campo String “vizinhos”. Uma sugestão: use uma lista de cidades, você poderá então percorrer essa lista e comparar as cidades próximas umas das outras e armazenar a quantidade de saltos em um contador.

Então eu esqueci de falar tenho que usar o metodo Random, para poder dar a quantidade em KM aleatória para as cidades cadastradas pelo usuário é depois imprimir as melhores rotas da cidade que o usuário está até a cidade escolhida, porém o professor não deu muita dica sobre como usar o Random, ele quis fazer a gente quebrar a cabeça, se puder fazer exemplos para me ajudar

Então eu esqueci de falar tenho que usar o metodo Random, para poder dar a quantidade em KM aleatória para as cidades cadastradas pelo usuário é depois imprimir as melhores rotas da cidade que o usuário está até a cidade escolhida, porém o professor não deu muita dica sobre como usar o Random, ele quis fazer a gente quebrar a cabeça, se puder fazer exemplos para me ajudar.

Então eu esqueci de falar tenho que usar o metodo Random, para poder dar a quantidade em KM aleatória para as cidades cadastradas pelo usuário é depois imprimir as melhores rotas da cidade que o usuário está até a cidade escolhida, porém o professor não deu muita dica sobre como usar o Random, ele quis fazer a gente quebrar a cabeça, se puder fazer exemplos para me ajudar…