Planche 1

Inf 431 -- Cours 3
Connexité 2


Plus courts chemins
http://jeanjacqueslevy.net
secrétariat de l'enseignement:
Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX,
01 69 33 34 67
http://www.enseignement.polytechnique.fr/informatique/IF

Planche 2

Plan


.65@percent
  1. Composantes fortement connexes -- Tarjan
  2. Fermeture transitive -- Warshall
  3. Plus courts chemins
  4. Plus court chemin -- Dijkstra

Planche 3

Connexité forte (1/11)

Composantes fortement connexes = parties maximales où toute paire de sommets distincts est reliée par un chemin.

Planche 4

Connexité forte (2/11)

(point d'attaches, cf. biconnexité)
Planche 5

Connexité forte (3/11)

(point d'attaches, cf. biconnexité)
Planche 6

Connexité forte (4/11)

(point d'attaches, cf. biconnexité)
Planche 7

Connexité forte (5/11)

(point d'attaches, cf. biconnexité)
Planche 8

Connexité forte (6/11)

(point d'attaches, cf. biconnexité)
Planche 9

Connexité forte (7/11)

point d'attaches en foncé
º premier sommet visité par dfs
Planche 10

Connexité forte (8/11)

Le graphe G'=(V',E') des composantes fortement connexes du graphe G=(V,E) est défini par:

Proposition 1 Le graphe G=(V',E') des composantes fortement connexes de G=(V,E) est acyclique.


mprimerComposanteDeRISLANCOIRfsilempilerepilerystemutrintrintln
Planche 11

Connexité forte (9/11)

[Tarjan, 72]
static int numOrdre;

static void imprimerCompFortementConnexes (Graphe g) {
  int n = g.succ.length; int num = new int[n]; numOrdre = -1;
  for (int x = 0; x < n; ++x) num[x] = -1;
  Pile p = new Pile(n);
  for (int x = 0; x < n; ++x)
    if (num[x] == -1)
      imprimerComposanteDe(g, x, num, p);
}

Planche 12

Connexité forte (10/11)

[Tarjan, 72]
static int imprimerComposanteDe (Graphe g, int x, int[ ] num, Pile p) {
  Pile.empiler(x, p);
  int min = num[x] = ++numOrdre;
  for (Liste ls = g.succ[x]; ls != null; ls = ls.suivant) {
    int y = ls.val; int m;
    if (num[y] == -1)
      m = imprimerComposanteDe (g, y, num, p);
    else m = num[y];
    min = Math.min (min, m);
  } 
  if (min == num[x]) { 
    int y; do {
      y = Pile.depiler(p);
      System.out.print (y + " ");
      num[y] = g.succ.length;  // équivalent à num[y] ¬ ¥
    } while (y != x);
    System.out.println();
    min = g.succ.length;
  } 
  return min;
}

Planche 13

Connexité forte (11/11)

Le point d'attache est le sommet en premier visité par dfs
Fin de dfs
Planche 14

Fermeture transitive (1/3)



Le graphe G+ = (V,E+) de la fermeture transitive de G+ = (V,E) est tel que E+ est minimum vérifiant
Planche 15

Fermeture transitive (2/3)

E matrice n× n d'adjacence pour un graphe avec n sommets.

On veut calculer
E+ = E + E2 + E3 + ···
  = E + E2 + E3 + ··· + En-1
puisque les chemins passant par des sommets distincts sont de longueur inférieure à n.

La multiplication de matrices n × n a une complexité O(n
3).

La fermeture transitive peut donc se faire en O(n
4) opérations.

Faire mieux?

Planche 16

Fermeture transitive (3/3)

Définition inductive des chemins selon le plus grand des noeuds intermédiaires par lesquels ils passent.

E
k est la fermeture transitive en n'utilisant des chemins passant par des sommets intermédiaires strictement inférieurs à k.
E0 = E
Ek+1 = Ek È {(x,y) | (x,k) Î Ek, (k,y) Î Ek }
[Warshall]
static Graphe fermetureTransitive (Graphe g) {
  int n = g.e.length;
  Graphe gplus = copieGraphe (g);
  for (int k = 0; k < n; ++k)
    for (int x = 0; x < n; ++x)
      for (int y = 0; y < n; ++y)
        gplus.e[x][y] = gplus.e[x][y] || (gplus.e[x][k] && gplus.e[k][y]);
  return gplus;
}

Complexité en O(n3) ou encore O(V3).

Planche 17

Plus courts chemins (1/2)

G=(V,E, d) est un graphe valué (d : V × V |® N).
d(x,y) est la distance de x à y.

On représente G par sa matrice d'adjacence d à valeurs entières.
On pose d(x,y) = +¥ si pas d'arc de x à y.

Planche 18

Plus courts chemins (2/2)

Plus courts chemins entre tous les sommets d'un graphe.

d
x,yk est la longueur du plus court chemin entre x et y passant par des sommets intermédiaires strictement inférieurs à k.
dx,y0= d(x,y)
dx,yk+1 = min{ dx,ykdx,kk + dk,yk }
[Floyd-Warshall]
static Graphe plusCourtsChemins (Graphe g) {
  int n = g.d.length;
  Graphe gplus = copieGraphe (g);
  for (int k = 0; k < n; ++k)
   for (int x = 0; x < n; ++x)
    for (int y = 0; y < n; ++y)
     gplus.d[x][y] = Math.min (gplus.d[x][y], gplus.d[x][k] + gplus.d[k][y]);
  return gplus;
}

Complexité en O(n3) ou encore O(V3). Espace mémoire en O(n2).

Floyd-Warshall = programmation dynamique (cf. cours 4).

Planche 19

Plus court chemin (1/5)

Plus court chemin entre deux sommets x et y dans un graphe valué. Soit dx,y sa longueur.
distx,x = 0
distx,z = min{distx,y + d(y,z) | 0 £ y < n}

Planche 20

Plus court chemin (2/5)

Plus court chemin entre un sommet x et tous les autres sommets. (Problème généralisé) mprimerComposanteDeheminMin
Planche 21

Plus court chemin (3/5)

[Dijkstra, 1959]
static int[ ] plusCourtChemin (GrapheV g, int x, int u) {
  int n = g.succ.length; int[ ] couleur = new int[n];
  int[ ] dMin = new int[n]; int[ ] chemin = new int[n];
  for (int t = 0; t < n; ++t) {
    couleur[t] = BLANC; dMin[t] = Integer.MAX_VALUE;
    chemin[t] = -1;
  }
  dMin[x] = 0;  couleur[x] = GRIS; int y;
  while ( (y = iMin(dMin, couleur)) != -1) {
    couleur[y] = NOIR;
    if (y == u)  return chemin;
    for (ListeV ls = g.succ[y]; ls != null; ls = ls.suivant) {
      int z = ls.val; int dyz = ls.d;
      if (dMin[y] + dyz < dMin[z]) {
        dMin[z] = dMin[y] + dyz;           // relaxation
        chemin[z] = y; couleur[z] = GRIS;
  } } }
  return chemin;
}

iMin(dMin, couleur) rend l'indice du minimum GRIS dans dMin

Planche 22

Plus court chemin (4/5)

[Dijkstra, 1959]
static int[ ] plusCourtChemin (GrapheV g, int x, int u) {
  int n = g.succ.length; int[ ] couleur = new int[n];
  int[ ] dMin = new int[n]; int[ ] chemin = new int[n];
  for (int t = 0; t < n; ++t) {
    couleur[t] = BLANC; dMin[t] = Integer.MAX_VALUE;
    chemin[t] = -1;
  }
  dMin[x] = 0;  couleur[x] = GRIS; int y;
  while ( (y = iMin(dMin, couleur)) != -1) {
    couleur[y] = NOIR;

    for (ListeV ls = g.succ[y]; ls != null; ls = ls.suivant) {
      int z = ls.val; int dyz = ls.d;
      if (dMin[y] + dyz < dMin[z]) {
        dMin[z] = dMin[y] + dyz;           // relaxation
        chemin[z] = y; couleur[z] = GRIS;
  } } }
  return chemin;
}

iMin(dMin, couleur) rend l'indice du minimum GRIS dans dMin

Planche 23

Plus court chemin (5/5)


Complexité en O(V2 + E), soit O(n2). Mémoire en O(n).

En utilisant des files de priorité pour retrouver le sommet à distance minimum et changer la distance par relaxation, on arrive à
Complexité en O((V+E) logV), soit O(n2 logn). Mémoire en O(n).

(On peut ramener à O(V logV + E), soit O(n
2) avec des tas de Fibonacci). [Fredman, Tarjan]

Exercice 1 Calculer le plus court chemin depuis tous les sommets jusqu'à un même sommet destination.

Exercice 2 Que se passe-t-il s'il y a des distances négatives?


Planche 24

Autres problèmes sur les graphes


Problème ouvert

Beaucoup de problèmes sur les graphes sont NP-complets.



This document was translated from LATEX by HEVEA.