human
Comment trouver les plus courts chemins de la source à tous les sommets en utilisant l'algorithme de Dijkstra avec C
gpt
L'algorithme de Dijkstra est très similaire à l'algorithme de Prim pour l'arbre couvrant minimum. Comme l'arbre couvrant minimum de Prim, générer un ACP (arbre de plus court chemin) avec une source donnée comme racine. Maintenir deux ensembles, un ensemble contient les sommets inclus dans l'arbre de plus court chemin, l'autre ensemble contient les sommets pas encore inclus dans l'arbre de plus court chemin. À chaque étape de l'algorithme, trouver un sommet qui est dans l'autre ensemble (ensemble pas encore inclus) et qui a une distance minimale par rapport à la source.

```
// Le programme vise à implémenter l'algorithme de plus court chemin de Dijkstra en C.
// Le programme utilise une matrice d'adjacence comme représentation du graphe

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

// Le nombre de sommets présents dans un graphe.
#define V 9

// Une fonction qui est utilisée pour identifier le sommet avec la plus petite valeur de distance
// parmi un ensemble de sommets qui n'ont pas encore été inclus dans l'arbre de plus court chemin.
int trouverDistanceMin(int dist[], bool sptSet[])
{
    // Initialiser la valeur minimale
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

// Une fonction utilitaire pour afficher la distance construite
// tableau
void afficherSolution(int dist[])
{
    printf("Sommet \t\t Distance depuis la source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t\t\t %d\n", i, dist[i]);
}

// une fonction qui applique l'algorithme de Dijkstra pour trouver le plus court chemin entre
// un seul nœud source et tous les autres nœuds d'un graphe. Le graphe est représenté en utilisant
// une matrice d'adjacence.
void dijkstra(int graph[V][V], int src)
{
    int dist[V];
    bool processed[V];
    int i, u, v;

    // Initialiser toutes les distances comme infinies et traitées comme fausses
    for (i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        processed[i] = false;
    }

    // La distance du sommet source à lui-même est toujours 0
    dist[src] = 0;

    // Trouver le plus court chemin pour tous les sommets
    for (i = 0; i < V - 1; i++) {
        // Choisir le sommet de distance minimale parmi l'ensemble de sommets non encore traités
        u = -1;
        for (i = 0; i < V; i++) {
            if (!processed[i] && (u == -1 || dist[i] < dist[u])) {
                u = i;
            }
        }

        // Marquer le sommet choisi comme traité
        processed[u] = true;

        // Mettre à jour la valeur de distance des sommets adjacents au sommet choisi
        for (v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !processed[v]) {
                int new_dist = dist[u] + graph[u][v];
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                }
            }
        }
    }

    // Afficher le tableau de distance construit
    afficherSolution(dist);
}


int main()
{
    /* Créer le graphe exemple */
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                        { 0, 0, 0