Chemins optimaux dans graphes algorithme de DANTZIG + programmation java

I. Introduction

1) Graphe valué.

On dit qu’un graphe G = (X,U) est valué si pour tout arc u

U on fait correspondre un réel l(u).

Si G = (X,U) est graphe valué

U. l(u) est appelé longueur ou valuation de l’arc u.

2) Chemin de longueur optimal.

On appelle problème du chemin optimal le problème suivant :

Trouver un chemin µ allant de sommet x au sommet y tq la longueur de µ : l(µ) =

soit optimal (optimal =

maximum ou minimum)

3) Condition d’existence :

Considérons un chemin de x à y : µ comprenant un circuit w de longueur négatif qui s’appel un circuit absorbant.

Soit µ’ le chemin de x à y sans emprunter le circuit w. Soit µ₁ le chemin de x à y en utilisant n fois le circuit w.

Donc le chemin min n’existe pas

Exemple: circuit de longueur négatif

La longueur du circuit suivant est -2. C’est donc un circuit absorbant.

1) Exemples :

Considérons la carte routière et cherchons la route la plus courte d’une localité à une autre.

Le graphe est obtenu de la façon suivante :

- Sommets correspondre aux localités

- Arcs correspondre aux routes (A chaque route on fait correspondre 2 arcs de sens opposés)

II. Algorithmes de résolution

Le problème du plus court chemin a été résolu par de nombreux algorithmes. Parmi ces algorithmes on peut trouver l’algorithme de

Ford, algorithme de DANTZIG(ou de MOORE-DIJKSTRA), algorithme de BELLMAN, etc. Différents problèmes peuvent être posés autour de la recherche de plus court chemin.

i. Un premier problème consiste à rechercher le plus court chemin entre deux points donnés. C’est-à-dire déterminer le chemin de plus petite longueur qui relie ces points.

ii. Un deuxième problème consiste à déterminer, à partir d’un point donné le plus court chemin pour aller à tous les autres

sommets.

iii. Enfin, un troisième problème consiste à trouver, pour n’importe quelle paire de sommets, le chemin le plus court entre eux.

1) Algorithme de Ford.

On suppose que le graphe G ne contient pas de circuit négatif G = (X,U) |X| = n.

1. Numéroter les sommets dans un ordre quelconque à

l’exception de l’origine et l’extrémité du chemin qui doivent être numérotés respectivement x₁et x_n

2. Affecter provisoirement, à tout sommet x_i un poids λ_i

0	si	i = 1
t.q λ_i =	si	i>1
+ ∞	si	i>1

3. Calculer de proche les différences λ_j – λ_i pour tout arc

(x_i,x_j)

, et remplacer λ_j par λ_i + l(i,j) si λ_j – λ_i >l(i,j)

4. Arrêter la procédure lorsqu’aucun λ_i ne peut plus être

modifié.

Soit λ_n^* la valeur final de λ_n. Donc la valeur du chemin minimal est λ_n^*.

2) Algorithme de DANTZIG

Soit x₁ l’origine et x_n l’extrémité entre lesquels on désire connaitre le chemin de longueur minimale [ l(u) ≥ 0,

U G = (X,U)]

(a) λ₁ = 0 E {x₁}

(b)

x_i

on associe x_i*

Ē = X – E t. q

(c) On pose

Puis on revient à (b) jusqu’on atteint x_n (si l’on veut seulement déterminer le chemin de v₀ minimale entre x₁ et x_n). Ou bien quand E = X (dans le cas où on désire connaitre les chemins de valeurs minimale entre x₁ et x_i

x_i

X – { x₁ }.

III. Implémentation de l’algorithme de DANTZIG.

Cet algorithme détermine la plus courte distance entre tous les couples de sommets d’un graphe valué G = (X,U). On suppose que le graphe ne contient pas de circuit absorbant. On commence par numéroter les sommets d’une manière quelconque. Ensuite, une matrice nommée MatMin de taille n x n (n= nombre de sommets) est construite indiquant pour chaque sommet la plus courte distance qui le sépare d’un autre sommet. L’idée est de considérer un sous-graphe pour lequel on détermine les plus courtes distances entre ses sommets. Ensuite, itérativement, on rajoute un sommet dans ce sous-graphe, on met les plus courtes distances à jour et on recommence jusqu’à ce que le sous-graphe soit le graphe lui même. Rappelant que dans ce TP on s’intéressera aux problèmes de type (iii).

A l’itération k, le sous-graphe a k sommets et ce sont ceux numérotés de 1 à k. A l’itération k + 1, on ajoute le sommet k + 1 dans le sous-graphe. Les distances sont mises à jour de la manière suivante. Tout d’abord on détermine la plus courte distance entre le sommet k + 1 et n’importe quel autre sommet. Cela s’exprime par:

MatMin(k + 1, i) = min{d(x_{k + 1},x_j) + MatMin(j,i)} pour i allant de

1 jusqu’à k. Cela veut dire que l’on considère que pour aller de k + 1 à i, on passe par un des sommets de 1 à k. On conserve la longueur du plus court chemin. De la même manière, on détermine

la plus courte distance entre n’importe quel sommet et le sommet k + 1.

MatMin(i,k + 1) = min{d(x_j,x_{k + 1}) + MatMin(i,j)} pour i = 1...k.

Enfin, on met à jour la plus courte distance de chaque sommet de 1 à k vers chaque sommet de 1 à k car peut être que le plus court chemin entre deux de ces sommets passe par k + 1.

MatMin(i,j) = min{MatMin(i,j) , MatMin(i,k + 1) + MatMin(k + 1,j)} pour i, j = 1...k.

Algorithme

Entrées: G = (X,U) un graphe.

Sorties: MatMin une matrice contenant les plus courtes distances.

Début

pour i ← 1 à n faire pour j ← 1 à n faire

si i = j alors MatMin(i,i) ← 0; sinon MAtMin(i,j) ← +∞;

fin pour; fin pour;

pour k ← 1 à n faire

pour i ← 1 à k - 1 faire

MatMin(k,i) ← min{d(x_k,x_j)+MatMin(j,i)|(x_k,x_j)

U};

fin pour;

pour i ← 1 à k - 1 faire

MatMin(i,k) ←min{d(x_j,x_k)+MatMin(i,j)|(x_j,x_k)

U};

fin pour;

pour i ← 1 à k - 1 faire pour j ← 1 à k - 1 faire

MatMin(i,j) ←min{MatMin(i,j),MatMin(i,k)+ MatMin(k,j)};

fin pour; fin pour;

fin pour;

Fin

Le corps de la classe AlgoDantzig

/**

* classe gérant les graphes

* @version 1.0

* @date 14/12/2016

import java.util.*; public class AlgoDantzig{

private Graphe gr; // le graphe

private float matMin[][]; // la matrice contenant les chemins optimaux entre les sommets

public AlgoDantzig(){

}

public AlgoDantzig(Graphe gr){

….

}

public void algorithm(){

….

}

public float[][] getMatriceMinimal(){

….

}

public static void main(String args[]){

….

}

Rechercher dans ce blog

Cours et Exercices