Remarques post-TP

La définition de graphe avec une matrice d’adjacence de taille MAX_NOEUD * MAX_NOEUD n’est pas optimale.

• soit on définit MAX_NOEUD très grand dès le départ
  \Rightarrow beaucoup de coefficients non utilisés
• sinon on change la valeur de la variable globale

Une manière meilleure

typedef struct graph {
    int vertices; // nb sommets
    int **adj;
} graphe;

Dans new_graph, il faut allouer la taille qu’il faut pour la matrice d’adjacence :

grph->vertices = m;
grph->adj = malloc(n * sizeof(int *));
for (int i = 0; i < n - 1; i++) {
    grph->adj[i] = malloc(n * sizeof(int));
}

Il faut écrire une fonction en plus pour libérer la mémoire.

Parcours en largeur, dijkstra, correction TP

void accessibles(graphe *grph, int src) {
    int *vus = malloc(grph->vertices * sizeof(int));
    int k;
    for (k = 0; k < grph->vertices; k++)
        vus[k] = 0;
    fifo *aVisiter = new_fifo();
    vus[src] = 1;
    push(aVisiter, src);
    while (aVisiter->taille != 0) {
        int i = take_first(aVisiter);
        for (int j = 0; j < grph->vertices; j++) {
            if (grph->adj[i][j] != 0 && vus[j] == 0) {
                vus[j] = 1;
                push(aVisiter, j);
            }
        }
        defiler(aVisiter);
    }
    print_acc(vus, grph->vertices, src);
    free(aVisiter);
    free(vus);
}

void dijkstra(graphe *grph, int src) {
    int n = grph->vertices;
    int *dist = malloc(n * sizeof(int));
    int *access = malloc(n * sizeof(int));
    int i, j, count;
    for (i = 0; i < n; i++) {
        dist[i] = INF;
        access[i] = 0;
    }
    dist[src] = 0;
    for (int k = 0; k < n - 1; k++) {
        int u = minDistance(grph, dist, access);
        access[u] = 1;
        for (j = 0; j < n; j++) {
            if (access[j] == 0 && grph->adj[u][j] != 0 &&
                dist[u] + grph->adj[u][j] < dist[j]) {
                dist[j] = dist[u] + grph->adj[u][j];
            }
        }
    }
    print_dist(dist, n, src);
    free(dist);
    free(access);
}

Le coefficient grph->adj[u][j] représente le poids d’une arête qui va de u vers j dans grph. On peut donc adopter aisément cet algorithme pour d’autres implémentations de graphes pour peu que l’on sache testéer s’il y a une arête de i vers j dans un graphe et en récupérer son poids.

int is_edge_in_adjlist(graphe *grph, int i, int j) {
    int test = 0;
    noeudListeAdj *n = grph->array[i].head;
    while (n != NULL && test == 0) {
        if (n->but == j)
            test = n->poids;
        n = n->suivant;
    }
    return test;
}

Ainsi, dans les algos précédents, il suffit de remplacer grph->adj[u][j] par is_edge_in_adjlist(grph, u, j) pour définir Dijkstra sans file de priorité.

Représentation par triplet

Supposons que l’on ait un graphe G à 15 sommets et une seule arête 0\ \underrightarrow{10}\ 1
Si on utilise une matrice d’adjacence pour représenter G, on va stocker 15 \times 15 + 225 coefficients dont… 224 zéros !
Or, il suffirait de connaître :

• 15 (nombre de sommets)
• (0, 1, 10) la seule arête de G

On peut éviter de stocker tous les zéros de la matrice d’adjacence en stockant de cette manière toutes les arêtes dans un vecteur contenant des triplets de la forme
(i, j, w) \leftrightarrow arête de i vers j de poids w dans G.

typedef struct triplet {
    int i;
    int j;
    int poids;
} triplet;

typedef struct graphe {
    int nbs;         /* nombre de sommets */
    int nba;         /* nombre d aretes */
    triplet *aretes; /* vecteur d aretes*/
} graphe;

Exemple

Nombre de sommets : S
Vecteur d’arêtes: (0, 4, 3), (0, 2, 18), (1, 0, 8), (2, 1, 4), (3, 1, 1), (4, 1, 10), (4, 3, 2)

Remarque

Pour déterminer s’il y a une arête de i vers j dans G, il suffit de parcourir le vecteur d’arêtes. C’est une opération en \Theta(a) où a est le nombre d’arêtes de G.

Représentation par brins

C’est une manière d’encoder un graphe introduite par Cori en 1973 ; très peu de références dans la littérature scientifique mais JJ aime bien alors voilà ¯\_(ツ)_/¯

Principe

On considère un graphe, dont on va numéroter les arêtes (si le graphe est pondéré, on peut garder les poids mais il faut des poids distincts)

Exemple

Une arête numérotée n va être séparée en deux parties :

• un brin -n vers le sommet d’où part l’arête
• un brin +n vers le sommet où arrive l’arête

On va ensuite associer à chaque sommet un brin (le premier brin), indiqué par le brin arrivant/sortant ou/du sommet avec la plus petite étiquette, et gardant son signe

Exemple

Ensuite, chaque brin est associé à un brin suivant en fonction du sommet qui lui est associé, ce brin suivant étant le premier que l’on rencontre en tournant autour du sommet dans le sens \circlearrowleft.

On aurait pu choisir l’autre convention, mais il faut être cohérent et garder le même.

Exemple

Question : Comment reconstruire un graphe de manière unique à partir de cette donnée ?
Exemple

On va construire un graphe à 3 sommets et 4 arêtes.

• le fait que le brin -4 soit associé au sommet 2 va indiquer que l’arête étiquetée 4 va partir du sommet 2
• le fait que le sommet 0 admette dans la ligne brin suivant le +4 indique que ce brin va arriver vers 0. On a donc une arête 2\ \underrightarrow{4}\ 0 et on peut ainsi reconstruire le graphe :
  

typedef struct strand {
    short int made;
    short next;
} strand;
typedef struct strandgraph {
    short int nbs;
    short int nba;
    short *made; // brim
    strand *nxt; // sommet et brim suivant
} strandgraphe;

Autres algos plus court chemin

Algo puissances de matrices d’adjacence (cf. Cours3)

Le nombre de chemin de longueur n d’un sommet i vers un sommet j est le coefficient (i, j) de la matrice M^{n}

(O -> 3)
k = 1
tant que M^{k}[0][3] == 0
    k+=1

Algo de Floyd-Warshall

Distance d’un plus court chemin \delta(u, v) entre deux sommets u et v pour toutes les paires (u, v)
G = (S, A) = S = \{s_{1}, \dots, s_{n}\}
On utilise une matrice M := M[i][j] = \begin{cases} 0\ p_{i} := J \\\\ w(s_{i}, s_{J})\ s_{i} j_{i}\ \overrightarrow{EA}\ s_{j} \\\\ \infty \text{ sinon} \end{cases}
Et on veut construire une matrice S(i, j) telle que \delta(S_{i}, J_{j})

Remarque

On peut avoir des poids négatifs

Exemple

Idée de l’algo :
P : v_{0} \underbrace{\rightarrow v_{1} \rightarrow v_{2} \dots \rightarrow v_{k-1}}\_\text{Intérieur de P} \rightarrow v_{k}
Un chemin d’intérieur vide est un chemin de la forme v_{k} ou v_{k} \rightarrow v_{k+1}
\delta(s_{i}, s_{j}) = un chemin dont l’intérieur est potentiellement contenu dans tout S
L’idée est que l’on va déchirer des chemins avec des intérieurs petits, et les autoriser à être de plus en plus grands

Soit I \leq S, soit \delta^{I}(u, v) la distance d’un plus court chemin d’intérieur inclus dans I.

Exemple

Propriété

\delta^{Iu\{x\}}(u, v) = \text{min}(\underbrace{\delta^{I}(u, v)}_\text{passer par x augmente la longueur du chemin}, \underbrace{\delta^{I}(u, x) + \delta^{I}(x, v)}_\text{passer par x améliore le ???})

void floyd_warshall(graphe *g) {
    int n = g->vertices;
    int dist[n][n];

    // Ici faut construire la matrice initiale

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // C'est du O(n³) donc ça pue un peu la merde
}

Algo de Belmann-Ford

C’est un algorithme de plus court chemin qui autorise d’avoir des arêtes avec des poids négatifs ; mais pas de cycles de poids négatifs

Exemple

\Rightarrow Le cycle 1\rightarrow 2\rightarrow 3\rightarrow 4 amène un chemin de longueur -2 de 1 vers lui-même. Ça n’a donc pas de sens de parler de plus court chemin de 0 vers 1.

Une partie importante de l’algo consiste à vérifier qu’il n’y a pas de cycle négatif, on s’en passera ici car on garde notre hypothèse de poids positifs !

Idée

On va calculer les longeurs des chemins les plus courts de longueur k, pour k++.

Observation

Les chemins les plus courts auront au plus n-1 arêtes ! (où n = nombre de sommets)

En effet

S’il y a plus de n arêtes, on passe par un sommet au moins 2 fois donc il y a forcément un cycle. Si ce cycle est de poids \geq 0, il est mauvais pour le plus court chemin donc on l’oublie. Il ne peut pas être de poids \leq 0.
De plus, un chemin de longueur du plus court chemin de src= u vers v avec au plus k arêtes.

On a alors :
\text{dist}^{k}[v] = \text{min}(\text{dist}^{k-1}[v], \text{dist}^{k-1}[w] + \text{poids}(w\rightarrow v))\ \text{pour tout voisin de }w\text{ et }v
Formule de réccurence !

Initialisation

\text{dist°}[u] = 0 \text{dist°}[w] = \text{INF} pour tout autre sommet

Exemple

Pour la représentation triplets :

void bellmanford(graphe *grph, int src) {
    int n = grph->nbs;
    int a = grph->nba;
    int u, v, poids;
    int *dist = malloc(n * sizeof(int));

    for (int k = 0; k < n; k++) {
        dist[k] = INF;
    }

    dist[src] = 0;

    for (int k = 0; k < n; k++) {
        for (int l = 0; l < a; l++) {
            u = grph->aretes[l].i;
            v = grph->aretes[l].j;
            poids = grph->aretes[l].poids;

            if (poids != 0 && dist[u] + poids < dist[v]) {
                dist[v] = dist[u] + poids;
            }
        }
    }

    print_dist(dist, n, src);
    free(dist);
}

Complexités