Best frist search

Main.java

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int[][] cities = {
            //0  1   2   3   4   5
            {-1, 20, 30, -1, -1, -1},
            {20, -1, 10, 50, -1, -1},
            {30, 10, -1, 40, -1, -1},
            {-1, 50, 40, -1, 30, 10},
            {-1, -1, -1, 30, -1, 90},
            {-1, -1, -1, 10, 90, -1}
    };
    static int[] heuristic = {10, 20, 30, 40, 50, 0};

    public static void main(String[] args) {
        ArrayList<Integer> current = new ArrayList<>();
        ArrayList<Pair<Integer, Integer>> choice = new ArrayList<>(); // first city , second heuristic
        choice.add(new Pair<>(0, 0));

        scanning(false);
        bfs(current, choice);

    }


    private static void bfs(ArrayList<Integer> current, ArrayList<Pair<Integer, Integer>> choice) {
        while (true) {
            ArrayList<Pair<Integer, Integer>> available = new ArrayList<>(); // first city , second heuristic
            current.add(choice.get(choice.size() - 1).getKey());

            if (reachGoal(current, choice)) break;

            addToAvailable(current, available, choice);

            theChoice(current, available, choice);

            printing(current, available, choice);
        }
    }

    private static void printing(ArrayList<Integer> current, ArrayList<Pair<Integer, Integer>> available, ArrayList<Pair<Integer, Integer>> choice) {
        System.out.print("current: " + current.get(current.size() - 1) + " | available: ");
        System.out.print("city: " + available.get(0).getKey() + ", heuristic: " + available.get(0).getValue());

        for (int i = 1; i < available.size(); i++) {
            System.out.print(", city: " + available.get(i).getKey() + ", heuristic: " + available.get(i).getValue());
        }
        System.out.println(" | choice: " + choice.get(choice.size() - 1).getKey());
    }

    private static void theChoice(ArrayList<Integer> current, ArrayList<Pair<Integer, Integer>> available, ArrayList<Pair<Integer, Integer>> choice) {
        Pair<Integer, Integer> min = findMinimum(current, available);
        choice.add(new Pair<>(min.getKey(), min.getValue() - heuristic[min.getKey()]));
    }

    private static Pair<Integer, Integer> findMinimum(ArrayList<Integer> current, ArrayList<Pair<Integer, Integer>> available) {
        Pair<Integer, Integer> min = new Pair<>(-1, -1);
        for (int i = 0; i < available.size(); i++) {
            if ((cities[current.get(current.size() - 1)][available.get(i).getKey()] != -1) &&
                    (min.getValue() == -1 || available.get(i).getValue() < min.getValue())
                    && (current.indexOf(available.get(i).getKey()) == -1)
                    )
                min = available.get(i);
        }
        return min;
    }

    private static void addToAvailable(ArrayList<Integer> current, ArrayList<Pair<Integer, Integer>> available, ArrayList<Pair<Integer, Integer>> choice) {
        for (int i = 0; i < cities.length; i++) {
            if (cities[current.get(current.size() - 1)][i] != -1 && current.indexOf(i) == -1) {
                int tmp = cities[current.get(current.size() - 1)][i] + choice.get(choice.size() - 1).getValue() + heuristic[i];
                available.add(new Pair<>(i, tmp));
            }
        }
    }

    private static boolean reachGoal(ArrayList<Integer> current, ArrayList<Pair<Integer, Integer>> choice) {
        if (heuristic[current.get(current.size() - 1)] == 0) {
            System.out.println("current: " + current.get(current.size() - 1));

            System.out.println("total: " + choice.get(choice.size() - 1).getValue());
            return true;
        }
        return false;
    }

    private static void scanning(boolean scan) {
        if (!scan) return;
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter # of cities: ");
        int n = scanner.nextInt();
        cities = new int[n][n];
        System.out.println("enter cities: ");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cities[i][j] = scanner.nextInt();
            }
        }

        System.out.println("enter heuristic: ");
        heuristic = new int[n];
        for (int i = 0; i < n; i++) {
            heuristic[i] = scanner.nextInt();
        }
    }
}

SampleOutput.txt

current: 0 | available: city: 1, heuristic: 40, city: 2, heuristic: 60 | choice: 1
current: 1 | available: city: 2, heuristic: 60, city: 3, heuristic: 110 | choice: 2
current: 2 | available: city: 3, heuristic: 110 | choice: 3
current: 3 | available: city: 4, heuristic: 150, city: 5, heuristic: 80 | choice: 5
current: 5
total: 80