Graphes : parcours et plus court chemin

Définition, notations

Un graphe est une structure de données non linéaires constituée de 2 types d’objets :

• des noeuds, ou sommets, contenus dans un ensemble S
• des arêtes, contenues dans un ensemble A, qui retient des sommets entre eux

Un graphe est dit orienté si toutes les arêtes sont équipées d’une certaine direction, indiquée par une flèche. Dans un graphe orienté, chaque arête a un sommet source et un sommet but (target)

Un graphe est dit pondéré si toutes les arêtes sont étiquetées par un nombre, encadrant généralement la distance entre 2 sommets. Ce nombre est appelé poids.

Dans ce cas, nous allons nous intéresser principalement à des graphes orientés et pondérés, par des poids entiers positifs (la positivité est indispensable pour l’algorithme de Dijkstra)

Parcours

Il existe plusieurs manières de parcourir / d’explorer un graphe, nous allons en voir 2 principales

Parcours en profondeur

• On part d’un sommet src = 1 à partir duquel on explore
• 1. On va créer une structure de pile (LIFO, Last In First Out) dans laquelle on va stocker les sommets parcourus
• 2. On cherche un voisin de l’élément en tête de pile (n’importe lequel, le premier que l’on rencontre), que l’on ajoute en tête de pile, et on répète tant que le nouveau sommet en tête de pile a toujours des voisins non utilisés
     
• 3. Lorsque ce n’est plus le cas, on dépile l’élément en tête, et on recherche un autre voisin du sommet précédent, et on l’ajoute en tête s’il y en a un ; sinon on dépile aussi, etc.
     
• On s’arrête lorsque la pile est vide. Au final, tous les sommets qui ont été stockés dans la pile ont été parcourus en partant de src = 1

Remarque

Évidemment, on parle de voisins non-déjà-parcourus, pour savoir ça, par exemple, on stoque dans un tableau de booléens pour savoir si le sommet à déjà été parcourus ou non.

Parcours en largeur

• On part d’un sommet src = 1 à partir duquel on explore
• 1. On va créer un structure de file (LIFO) dans laquelle on place src
• 2. On ajoute ensuite tous les voisins de src dans la file (idem, dans n’importe quel ordre), puis on supprime l’élément src
• On recommence ensuite avec le premier voisin en tête de file, on ajoute ses voisins à la fin, etc.
  
• 3. Si on arrive sur un sommet qui n’a plus de voisins non-déjà-parcouru, on le supprime de la file
     
• Le parcours s’arrête lorsque la file est vide. Tous les sommets qui ont été stockés dans la file ont été parcourus en partant de src = 1

Remarque

• Pour un graphe non-orienté, le graphe est connexe si et seulement si tous les sommets sont exploités à partir d’un parcours partant de n’importe quel sommet
• On peut dessiner l’ordre couvrant dans ce cas en gardant trace du parent à chaque ajout d’un sommet dans la file

Algorithme de Dijkstra

C’est un algorithme permettant de trouver le plus court chemin entre 2 sommets dans un graphe pondéré

Paramètres de l’algorithme :

• un graphe orienté pondéré avec des nombres positifs
• un sommet src à partir du quel on va renvoyer un tableau sous la forme

Avec d_{i} la distance de src au sommet s_{i} la plus petite

Initialisation

On crée un tableau de taille n qu’on remplit avec :

• INF/9999 pour les sommets différents de src
• 0 pour src

Traitement

Commençons par traiter le sommet src et tous ses arcs sortants
On va regarder toutes les arêtes sortantes de a, dans un ordre quelconque

• Arc de 0 vers 2, longueur 18, qui est mieux que la valeur précédente INF dans dist[2]
  \Rightarrow On change la valeur dist[2] en 18.
• Arc de 0 vers 4, longueur 3
  \Rightarrow On change la valeur dist[4] en 3.

• On va ensuite choisir un autre sommet
  • Peut on prendre n’importe lequel des deux rencontrés ? NON!!
  • \Rightarrow L’algorithme de Dijkstra impose de choisir celui qui est situé à la plus petite distance \rightarrow ici 4 !
• On traite donc 4 :
  • L’arc 4 \rightarrow 3 de longueur 2 permet de mettre 5 = dist[4] + 2 dans dist[3]
  • L’arc 4 \rightarrow 1 de longueur 10 permet de mettre 13 = dist[4] + 10 dans dist[1]
    À ce stade :

• On recomence avec le sommet non traité qui a la plus petite distance : 3
  • L’arc 3 \rightarrow 1 de longueur 1 permet de découvrir un chemin de longueur 6 = \textbf{dist[3] + 1} de 0 vers 1, qui est meilleur que le 13 précédent \Rightarrow on change donc dist[1] en 6

• On traite ensuite 1 :
  • L’arc 1 \rightarrow 0 permet de découvrir un chemin de longueur 14 de a vers a
    \Rightarrow Pas meilleur que le 0 précédent, donc on ne change rien
  • L’arc 1 \rightarrow 2 permet de découvrir un chemin de longueur 10 de a vers c, mieux que le 18 précédent
• On traite ensuite 2 :
  • Pas d’arc sortant \Rightarrow aucune modification
• On a alors traité tous les sommets, l’algorithme s’arrête et notre résultat est :

Commentaires

Pour savoir quels sommets ont étés parcourus ou non, on va initialiser un tableau de booléens (comme dit précédemment) contenant des 0, et on change la valeur à 1 lorsque le sommet est traité. Avant de traiter un nouveau sommet, il faut donc bien vérifier qu’il est toujours à 0 dans ce tableau.

• Comment sélectionner le sommet à la plus petite distance pour le traiter juste après ? Il y a plusieurs possibilités :
  • On peut écrire une fonction minDistance qui parcourt les sommets adjacents et sélectionne celui de plus petit poids

Exemple

#include <stdlib.h>

#define INF 9999

// S'il manque des trucs dans le code, c'est dans les exemples plus bas.

/* Fonction permettant de trouver le sommet à plus petite distance
parmis les sommets pas encore parcourus, sans utiliser de pile de priorité */
int minDistance(int dist[], int access[]) {
    int min = INF, min_index;
    int i;
    for (int i = 0; i < MAX_NOEUD; i++)
        if (access[i] == 0 && dist[i] <= min)
            min = dist[i], min_index = i;
    return min_index;
}

// TODO: Faire une fonction poour récupérer le poids? idk

/* Algorithme de Dijkstra */
void dijkstra(graphe *g, int src) {
    int n = g->vertices;

    int *dist = malloc(n * sizeof(int));
    int *acces = malloc(n * sizeof(int));

    int i, j, count;
    for (i = 0; i < n; i++) {
        dist[i] = INF;
        acces[i] = 0;
    }

    dist[src] = 0;
    for (count = 0; count < n - 1; count++) {
        int u = minDistance(dist, acces);
        acces[u] = 1;
        for (j = 0; j < n; j++) {
            if ((acces[j] == 0) && poids(/* u->j */) != 0 && dist[u] != INF &&
                dist[u] + poids(/* u->j */) < dist[j]) {
                dist[j] = dist[u] + poids(/* u->j */);
            }
        }
    }
}

• Sinon, il faut stocker les sommets adjacents dans une structure adaptée appellée file de priorité.
  C’est une file dans laquelleles tâches de plus petites valeur enfiler -> 16 15 12 5 -> défiler

Implémentation possibles :

1. Un tableau

   • Enfiler : Rajouter à la fin du tableau
   • Défiler : Parcourir toutes les tâches jusqu’à trouver le minimum.

2. Un tableau trié

   • Défiler : Retirer l’élément au début du tableau qui est le minimum
   • Enfiler : Il faut trouver où insérer l’élément à la bonne place

3. (Mieux) Un tas binaire
   C’est un arbre binaire presque complet (chaque niveau est rempli complètement sauf éventuellement le dernier) dans lequel chaque tâche est plus prioritaire que ses enfants
   -> La tâche la plus prioritaire (le minimum est la racine)
   

• Enfiler : On insère où il y a une place de libre, en veillant à garder la propriété de tas linéaire
  • si la tâche est moins prioritaire, on laisse
  • sinon, on échange avec le parent et on répète tant qu’il le faut
    
• Défiler :
  • On enlève l’évènement la plus prioritaire qui est à la racine
  • On place le dernier élément en bas à droite à la racine et on compose : \begin{cases} \text{racine} \\\\ \text{racine}(\text{fils}-\text{g}) \\\\ \text{racine}(\text{fils}-\text{d})\end{cases}
    Et on met le plus petit en haut
    
    Ces 2 opérations sont en \Theta(log(n)) : elles se font sur la hauteur d’une branche

Matrices d’adjacences

On peut encoder tout un graphe (orienté ou non, pondéré ou non), par une matrice de taille n\times n appelée matrice d’adjacence.
M[i][j] := \begin{cases} 1 \text{ s'il y a une arête de i vers j} \\\\ 0 \text{ sinon}\end{cases}

Remarque: il y a autant de 1 que de nombre d’arêtes dans le graphe.

On peut aussi définir une matrice d’adjacence pour un graphe non-orienté :

• Dans ce cas, s’il y a une arête de i vers j, il y en a aussi une de j vers i
  \Rightarrow M[i][j] = M[j][i] (la matrice d’ordonnance est symétrique)
  

Remarque: il y a 2x le nombre d’arêtes que de 1.

• Idem pour un graphe pondéré :
  \Rightarrow M[i][j] = \begin{cases} \text{poids(i}\rightarrow\text{j) s'il y a une arête de i vers j} \\\\ 0 \text{ sinon}\end{cases}
  

Remarque: nombre de coefficients non nuls vaut le nombre d’arêtes

#define MAX_NOEUD 15

typedef struct graphe {
    int vertices;
    int adj[MAX_NOEUD][MAX_NOEUD];
} graphe;

/* Fonction qui crée un graphe vide (sans arêtes) à n sommets. */
graphe *newgraph(int n) {
    graphe *grph;
    grph = malloc(sizeof(*grph));
    if (grph == NULL) {
        fprintf(stderr, "Erreur : Probleme creation Graphe.\n");
        exit(EXIT_FAILURE);
    }
    grph->vertices = n;
    int i, j, w;
    float v;
    srand(time(NULL));
    for (i = 0; i < MAX_NOEUD; i++) {
        for (j = 0; j < MAX_NOEUD; j++) {
            grph->adj[i][j] = 0;
        }
    }
    return grph;
}

/* Affiche le nombre de sommets et la matrice d'adjacence */
void display(graphe *grph) {
    printf("Nombre de sommets : %d. \n", grph->vertices);
    printf("Matrice d'adjacence : \n");
    int i, j;
    for (i = 0; i < MAX_NOEUD; i++) {
        for (j = 0; j < MAX_NOEUD; j++) {
            printf("%d", grph->adj[i][j]);
            printf(j < MAX_NOEUD - 1 ? "\t" : "\n");
        }
    }
}

/* Ajoute une arête d'un sommet i vers un sommet j (avec poids) */
void add_edge_weight(graphe *grph, int i, int j, int weight) {
    grph->adj[i][j] += weight;
}

/* Ajoute une arête d'un sommet i vers un sommet j (sans poids) */
void add_edge(graphe *grph, int i, int j) { grph->adj[i][j] += 1; }

/* Supprime une arête (avec ou sans poids) de i vers j */
void remove_edge(graphe *grph, int i, int j) {
    if (grph->adj[i][j] == 0) {
        printf("Il n'y a pas d'arête à supprimer. ");
    } else {
        grph->adj[i][j] = 0;
        printf("Arête de %d vers %d supprimée. \n", i, j);
    }
}

Propriété (matrice adjacence)

Si G est un graphe (non) orienté de matrice d’adjacence A, le nombre de chemins de longueur n d’un sommet i vers un sommet j est égal au coefficient (i, j) de la matrice A^{n}

Ceci fournit un autre algo de parcours/plus court chemin…

• On calcule toutes les puissances successives A^{k} (k \geq 1) de A par exponentiation rapide, et on arrête si on trouve un entier n tel que \begin{cases} A^{n}(i, j) \neq 0 \\\\ A^{n}(i, j) = 0 \quad \forall \ k < n \end{cases}

Listes d’adjacences

Un graphe à n sommets peut aussi être représenté par un tableau de n listes contenant chacune les successeurs en question.

En C, on va représenter ces listes par des listes chaînées

Sachant qu’on veut aussi accéder au poids des arêtes, on va encoder un noeud d’une liste d’adjacence par :

typedef struct nodeAdjList {
    int target;
    int weight;
    struct nodeAdjList *next;
} nodeAdjList;

typedef struct AdjList {
    struct nodeAdjList *head;
} AdjList;

On peut ensuite représenter un graphe comme suit :

typedef struct graphe {
    int vertices;
    struct AdjList *array;
} graphe;

\Rightarrow Encodant le nombre de sommets et un tableau de listes d’adjacences

/* Fonction qui crée un graphe vide (sans arêtes) à n sommets. */
graphe *newgraph(int n) {
    graphe *grph = malloc(sizeof(*grph));
    grph->vertices = n;
    grph->array = (AdjList *)malloc(n * sizeof(struct AdjList));
    for (int i = 0; i < n; ++i)
        grph->array[i].head = NULL;
    return grph;
}

/* Ajoute une arête avec un poids */
void add_edge(graphe *grph, int src, int target, int weight) {
    if (weight == 0)
        return;
    nodeAdjList *Node = new_nodeAdjList(target, weight);
    Node->next = grph->array[src].head;
    grph->array[src].head = Node;
}

/* Fonction qui affiche une liste d'adjacence */
void print_adjlist(struct graphe *grph) {
    int v;
    for (v = 0; v < grph->vertices; v++) {
        nodeAdjList *temp = grph->array[v].head;
        printf("\n Liste d'adjacence de %d : \n head ", v);
        while (temp != NULL) {
            printf("-> (%d, %d)", temp->target, temp->weight);
            temp = temp->next;
        }
        printf("\n");
    }
}

/* Génération d'un graphe aléatoire, en stockant les poids des arêtes qu'on
 * ajoute dans un tableau n*n */
graphe *remplirgraphe(int n) {
    graphe *grph = newgraph(n);
    int i, j, w, num, max;
    float v, taux;
    max = n * n;
    taux = 25.0;
    num = n / 10;
    while (num > 1) {
        num /= 5;
        taux /= 3.0;
    }
    taux /= 100.0;
    srand(time(NULL));
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            v = (float)rand() / (float)RAND_MAX;
            add_edge(grph, i, j, v < taux ? (int)(v * 100.) : 0);
        }
    }
    return grph;
}