Blog de Nico-pyright(c)

17
septembre
2010

[C] Implémentation de l’algo de Dijkstra en C

Un article de nico-pyright(c) Comments

J’ai eu besoin d’utiliser l’algo bien connu de Dijkstra pour trouver un plus court chemin entre 2 points. Le principe est très bien expliqué sur wikipédia, mais j’avais besoin d’une implémentation en C.

Après quelques recherches, je suis tombé sur cette page qui m’offre l’aglo tout cuit, mais sans son utilisation.

Je montre ici comment l’utiliser après une ou deux corrections de coquille dans l’algo trouvé.

Il faut dans un premier temps une matrice adjacente, qui peut être de cette forme :

#define INFINI 10000
#define NB_SOMMET 6
  
int mat[NB_SOMMET][NB_SOMMET] =  
    {{ 0, 171, INFINI, INFINI, INFINI, INFINI},
    {171,   0,  30, INFINI, INFINI, INFINI},
    {INFINI,  30,   0, INFINI,  39,  13},
    {INFINI, INFINI, INFINI,   0,  30, INFINI},
    {INFINI, INFINI, 39,   30,   0,  26},
    {INFINI, INFINI,  13, INFINI,  26,   0}};

On a une constante “Infini” qui est suffisamment grande, c’est à dire plus grande que la distance maxi entre 2 sommets. Et une matrice carrée contenant la distance entre chaque sommet.

Ensuite la méthode avec les 2-3 trucs corrigés :

void dodijkstra(int sr,int ds, int path[])
{
    if (sr == ds)
        return;
  
    struct node
    {
        int pre;   /* Predecessor */
        int length; /* Length between the nodes */
        enum {perm,tent} label; /* Enumeration for permanent and tentative labels */
    }state[NB_SOMMET];
        
        int i,k,min;
        struct node *p;
        /* Initialisation of the nodes aka First step of Dijkstra Algo */
        for(p=&state[0];p<&state[NB_SOMMET];p++)
        {
           p->pre= -1;
           p->length=INFINI;
           p->label=node::tent;
        }
        state[ds].length=0; /* Destination length set to zero */
        state[ds].label=node::perm; /* Destination set to be the permanent node */
        k=ds; /* initial working node */
        /* Checking for a better path from the node k ? */
        do
        {
           for(i=0;i<NB_SOMMET;i++)
              {
                  if(mat[k][i]!=0 && state[i].label==node::tent)
                     {
                        if((state[k].length+mat[k][i])<state[i].length)
                           {
                               state[i].pre=k;
                               state[i].length=state[k].length+mat[k][i];
                           }
                     }
              }
             k=0;
             min=INFINI;
              /* Find a node which is tentatively labeled and with minimum label */
              for(i=0;i<NB_SOMMET;i++)
              {
                 if(state[i].label==node::tent && state[i].length<min)
                    {
                        min=state[i].length;
                        k=i;
                    }
              }
              state[k].label=node::perm;
        } while(k!=sr);
        
        i=0;
        k=sr;
        /* Print the path to the output array */
        do 
        {
            path[i++]=k;
            k=state[k].pre;
        } while(k>=0);
        path[i]=k;
}

et enfin, l’appel de la méthode :

int path[150];
for (int z = 0 ; z < 150 ; z++)
    path[z] = -1;
dodijkstra(sommetSource, sommetDestination, path);

On initialise le tableau de résultat. Ici j’ai pris 150 arbitrairement, le but est que le tableau puisse contenir toutes les étapes intermédiaires.

L’algorithme nous rempli le tableau avec le trajet optimal.

path[0] contiendra la source
path[i] contient les différents sommets intermédiaires
path[n] contient la destination
path[n->150] contient -1

Identifiez-vous

Créer un compte

Blog de Nico-pyright(c)

Laisser un commentaire

Articles récents

Commentaires récents

Archives

Catégories

Méta

Identifiant
Mot de passe

Mot de passe oublié ?