human
Écrivez du code Java qui peut calculer le coût minimum pour connecter toutes les villes
gpt
L'objectif est d'établir le chemin le plus rentable reliant toutes les villes. Pour cela, nous devons déterminer l'Arbre Couvrant Minimum (ACM) de la carte de la ville, en traitant chaque ville comme un nœud sur le graphe et toutes les routes endommagées comme des arêtes. Le coût total du chemin est la somme des valeurs des arêtes dans l'Arbre Couvrant Minimum.

```
// Code Java pour trouver le chemin de coût minimum
// pour connecter toutes les villes
import java.util.* ;

class GFG{

    // Fonction pour trouver le nœud de valeur minimale
    // parmi les nœuds qui ne sont pas encore inclus dans l'ACM

    static int minNode(int n, int keyvals[], boolean mstset[])
    {
        int min_val = Integer.MAX_VALUE;
        int min_index = 0;

        // Parcourir toutes les valeurs des nœuds,
        // qui ne sont pas encore inclus dans l'ACM et trouver celui de valeur minimale.
        for(int i = 0; i < n; i++)
        {
            if (mstset[i] == false && keyvals[i] < min_val)
            {
                min_val = keyvals[i];
                min_index = i;
            }
        }
        return min_index;
    }

    // Fonction pour trouver l'ACM et
    // le coût de l'ACM.
    static void findCost(int n, int city[][])
    {

        // Tableau pour stocker les nœuds parents.
        int parent[] = new int[n];

        // Tableau pour stocker la valeur clé de chaque nœud.
        int keyvals[] = new int[n];

        // Tableau booléen pour indiquer si un nœud est inclus dans l'ACM ou non.
        boolean mstset[] = new boolean[n];

        // Définir toutes les valeurs clés comme infinies et aucun des nœuds n'est inclus dans l'ACM.
        for(int i = 0; i < n; i++)
        {
            keyvals[i] = Integer.MAX_VALUE;
            mstset[i] = false;
        }

        // Commencer à trouver l'ACM à partir du nœud 0.
        // Le parent du nœud 0 est aucun et est défini à -1.
        // La valeur clé ou le coût minimum pour atteindre le nœud 0 à partir du nœud 0 est 0.
        parent[0] = -1;
        keyvals[0] = 0;

        // Trouver les n-1 autres nœuds de l'ACM.
        for(int i = 0; i < n - 1; i++)
        {    
            // Tout d'abord, trouver le nœud de valeur minimale parmi les nœuds qui ne sont pas encore inclus dans l'ACM.
            int u = minNode(n, keyvals, mstset);

            // Inclure le nœud u dans l'ACM.
            mstset[u] = true;

            // Mettre à jour les valeurs des nœuds voisins de u qui ne sont pas encore inclus dans l'ACM.
            for(int v = 0; v < n; v++)
            {
                if (city[u][v] > 0 && mstset[v] == false && city[u][v] < keyvals[v])
                {
                    keyvals[v] = city[u][v];
                    parent[v] = u;
                }
            }
        }

        // Trouver le coût en ajoutant les valeurs des arêtes de l'ACM.
        int cost = 0;
        for(int i = 1; i < n; i++)
            cost += city[parent[i]][i];

        System.out.println(cost);
    }

    // Code principal
    public static void main(String args[])
    {

        // Entrée 1
        int n1 = 5;
        int city1[][] = { { 0, 1, 2, 3, 4 },
                        { 1, 0, 5, 0, 7 },
                        { 2, 5, 0, 6, 0 },
                        { 3, 0, 6, 0, 0 },
                        { 4, 7, 0, 0, 0 } };

        findCost(n1, city1);

        // Entrée 2
        int n2