Salut, 

Récemment, je fais un petit programme en C qui permet de lire des graphes (avec pondération entre les arcs) et qui permet d'explorer les chemins les plus court à partir d'un sommet initial.

Voici mon sous programme qui permet cette exploration à partir d'un fichier texte (lecture dans le main)  : 

int pcc_Dijkstra(Graphe* g, int s0)
{
    for(int i = 0; i < g->ordre; i++)
    {
        g->pSommet[i]->couleur = 0;
    }

    g->pSommet[s0]->couleur=1;
    g->pSommet[s0]->distance = 0;
    g->pSommet[s0]->marquage = 1;

    pArc temp = g->pSommet[s0]->arc;

    int nouveau_s0 = 0;
    float poids = 999.0;


    // boucle de parcours
    while(!(temp == NULL))
    {
        g->pSommet[temp->sommet]->predecesseur=s0;

        if(g->pSommet[temp->sommet]->couleur == 0 && (g->pSommet[temp->sommet]->valeur != g->pSommet[s0]->predecesseur))
        {
            printf("\nOn visite un sommet voisins de %d :", s0);
            printf(" \n- le sommet %d", g->pSommet[temp->sommet]->valeur);
            printf("distance sommet 8 = %f", g->pSommet[8]->arc->poids);
            g->pSommet[temp->sommet]->couleur = 1; // pour ne pas visite 2 fois son sommet voisin
            g->pSommet[temp->sommet]->distance = g->pSommet[temp->sommet]->arc->poids;

            printf("\nDistance avec son predecesseur (%d) : %f\n",  g->pSommet[temp->sommet]->predecesseur, g->pSommet[temp->sommet]->arc->poids);
            printf("On le compare au poids %f\n\n", poids);

            if((g->pSommet[temp->sommet]->arc->poids) < poids) // si on trouve une distance plus courte
            {
                if(  g->pSommet[temp->sommet]->distance > 0)
                {
                    g->pSommet[temp->sommet]->distance = g->pSommet[temp->sommet]->arc->poids;
                }
                else
                {
                    printf("addition de plusieurs distances");
                    g->pSommet[temp->sommet]->distance = g->pSommet[temp->sommet]->distance + g->pSommet[temp->sommet]->arc->poids;
                    printf(" --> %f", g->pSommet[temp->sommet]->distance);
                }

                poids = g->pSommet[temp->sommet]->distance;
                nouveau_s0 = g->pSommet[temp->sommet]->valeur;
                g->pSommet[temp->sommet]->marquage=1;
            }
            else
            {
                g->pSommet[temp->sommet]->distance = poids;
            }
            printf("\n--> Distance la plus courte: %f \n", g->pSommet[temp->sommet]->distance);
        }

        temp = temp->arc_suivant;
    }
    printf("\n On a fini de visite tous les voisins de %d\n", s0);
    printf("\nOn repars du sommet %d\n", nouveau_s0);
    s0 = nouveau_s0;

    return s0;

}

et on l'appelle a chaque fois qu'on trouve le chemin le plus court entre les sommets (donc dans une boucle qui fait 1 par 1 tout les sommets du graphe)

Voici quelques illustrations, comment est lu le fichier texte : 

Et voici le graphe dessiné : 

Mon problème, c'est que le sommet 8 va toujours avoir en mémoire la "distance" entre le sommet 0 et lui-même, alors que on repart tout bonnement des autres sommets (en somme, si je pars du 4, en allant au 8, on m'affiche la distance entre les deux de "16" alors qu'elle correspond à l'arc de 0 à 8 !)

Je vais faire une bonne pause, mais vu que pour beaucoup vous êtes des cracks ici, peut être que vous avez trouvez l'erreur avant moi. 

Je peux apporter des précisions au code sur demande, meme le header ou le main.

Merci d'avance

-
Edité par Clément 2910 24 septembre 2022 à 16:36:57

Il manque

• la définition de Graphe
• une explication claire de ce que ça devrait faire. Parce que faire écrire "addition de plusieurs distances", ça le fait pas trop.

-
Edité par michelbillaud 24 septembre 2022 à 20:04:04

Ce qui fait 16 entre le sommet 0 et le sommet 8, c'est le poids de l'arc.
Quand tu parcours l'arbre, par exemple, pour un parcours qui part du sommet 0.
a) 0 -> 8 : distance du sommet 8 : (distance du som 0 : 0) + (arc 0->8 : 16) = 16
b) 0 -> 1 : distance du sommet 1 : (distance du som 0 : 0) + (arc 0->1 : 1) = 1
c) 0 -> 7 : distance du sommet 7 : (distance du som 0 : 0) + (arc 0->7 : 13) = 13
d) 1 -> 8 : distance du sommet 8 : (distance du som 1 : 1) + (arc 1->8 : 5) = 6 (remplace le 16 car plus petit)

Je ne sais pas comment du stocke le poids des arc, mais il ne faut pas le confondre avec ton sommet->distance qui représente la distance du début du parcours au sommet courant.

Je n'ai pas l'impression que tu additionnes les distances quand tu passes d'un noeud à un autre.
Tu as l'air d'avoir deux flags: couleur et marquage. À quoi ça sert? Un seul devrait suffire.

Il me semble qu'au départ on met la distance à soi-même à 0 et "infini" aux autres.

Et on va vers le noeud ayant la pplus courte distance entre la valeur actuelle et le nouveau parcours ...

La valeur "infini" peut être la somme de toutes les pondérations du graphe plus un.

-
Edité par PierrotLeFou 24 septembre 2022 à 19:09:53

La valeur INFINITY est une macro définie dans math.h

#include <stdio.h>
#include <math.h>

int main() {
	printf("infinity = %f\n", INFINITY);
	return 0;
}

Si le codage des flottants le permet, c'est l'infinité positive, sinon un grand nombre non représentable par un float, et du coup ça provoque un diagnostic à la compilation, crois-je comprendre du standard. 

Chez moi ça marche (tm)

$ make a
cc     a.c   -o a
$ ./a 
infinity = inf

Remarque sur le code

Quand tu écris

    // boucle de parcours
    while(!(temp == NULL))
    {

• le commentaire est inutile. Tout le monde sait que while, c'est pour faire une boucle, et qu'une boucle, ça parcourt quelque chose
• donc ça serait bien de dire quoi. Tous les sommets ? Tous les arcs ? tous les arcs issus d'un sommet ?
• et ça t'aiderait à t'y retrouver dans ton code (ce qui est pratique quand on est en train de l'écrire).

pArc temp = g->pSommet[s0]->arc;
 
while(!(temp == NULL))
    // .... 
        temp = temp->arc_suivant;
    }

// pour tout arc issu de s0
for (pArc parc = g->pSommet[s0]->arc; parc; parc = parc->suivant) {
   // ....
}
 

-
Edité par michelbillaud 24 septembre 2022 à 20:18:17

Pourquoi as-tu appelé ta fonction Dijkstra ?

https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Ça devrait être un algorithme de parcours en largeur effectué de préférence de façon récursive.
À partir d'un noeud, on regarde en boucle tous les noeuds accessibles (ses voisins).
On compare la longueur cumulée dans ce noeud plus la longueur de l'arc avec la longueur déjà enregistrée dans le noeud voisin.
Si la somme est plus petite, on place cette somme dans le voisin et on continue en récursif sur le voisin, sinon on passe ce noeud voisin.

Si le voisin est le noeud de sortie ou noeud destination, on retourne simplement sa longueur cumulée sans rien faire d'autre.
Si on ne peut pas avancer sur un voisin, on considère que la longueur est infinie dans cette direction.
À la fin de la boucle, on place dans le noeud courant le voisin le plus approprié (meilleur) et on retourne à l'appelant la plus petite des longueurs .
Si aucun voisin n'est approprié, on retourne infini à l'appelant.
De cette façon, on n'a pas besoin de marquage, car toute boucle fera augmenter la longueur et cette direction ne sera pas favorisée.

Une pondération nulle ne devrait pas être acceptée.
Au retour de l'appel initial, on obtient la longueur du plus court chemin.
Et on peut suivre les noeuds appropriés (meilleurs) pour retrouver ce chemin.

Je suppose que tes pondérations ne sont pas astronomiques. Tu pourrais comparer toute somme avec INFINITY.
Ceci marche et donne OK
-
#include <stdio.h>
#include <math.h>
int main(void) {
    double arc = 1.0e255;
    if(arc < INFINITY) printf("OK");
}

edit:
J'ai essayé de modifier ton code pour refléter mon idée sur l'algorithme.
Je n'ai pas les structures et pas de graphe pour tester.
C'est en tout cas la bonne idée ...
J'ai ajouté le champs  meilleur  pour chaque noeud qui est le meilleur noeud // arc sortant.
-
int pcc_Dijkstra(Graphe* g, int sommet) {
    pArc arc = g->pSommet[sommet]->arc;
     if(arc == NULL) return g->pSommet[sommet]->distance;
    int meilleur = -1;
    double minimum = INFINITY;
    while(arc) {
        int distance = g->pSommet[sommet]->distance + arc->poids;
        if(distance < g->pSommet[arc->sommet]->distance) {
            g->pSommet[arc->sommet]->distance = distance;
            distance = pcc_Dijkstra(g, arc->sommet);
            if(distance < minimum) {
                minimum = distance;
                meilleur = arc->sommet;
            }
        arc = arc->arc_suiv;
    }
    g->pSommet[sommet]->meilleur = meilleur;
    return minimum;
}
 
int main(void) {
    // On a généré le graphe.
    for(int i = 0; i < g->ordre; i++) {
        g->pSommet[i]->distance = INFINITY;
    }
    int s0 = 0;   // On trouve le noeud entrant.
    g->pSommet[s0]->distance = 0;
    int optimal = pcc_Dijkstra(g, s0);
    printf("La longueur du chemin le plus court est %d\n", optimal);
    printf("%d ", s0);
    do {
        s0 = g->pSommet[s0]->meilleur;
        printf("%d ", s0);
    } while(g->pSommet[s0]->arc);
    printf("\n");
}

-
Edité par PierrotLeFou 25 septembre 2022 à 7:58:48

Clément 2910 a écrit:

Je sais qu'il y a plein de petits soucis, néanmoins celui que je veux résoudre c'est : pourquoi (alors que je vise le sommet 1, 2 , 3 mais pas le 0) on obtient le poids de l'arc de 0 à 8 tout le temps et pas de 1,2,3... à 8 ? Est ce que vous pensez que ça vient de ce sous programme ?

De quoi ça pourrait venir d'autre chose que du code que tu fais tourner ?

 Les "petits soucis" ne sont pas secondaires. Souvent, c'est la cause des grands. Exemple: mauvais choix de noms de variables => confusion => erreur

-
Edité par michelbillaud 25 septembre 2022 à 7:44:26

-
Edité par PierrotLeFou 25 septembre 2022 à 8:05:18