[PDF] Diapositive 1 Beaucoup d'algorithme de calcul

View - Download Diapositive 1

Previous PDF

Next PDF

Algorithmes de plus

court chemin Heike Ripphausen-Lipa-BeuthUniversity of Applied Science -Berlin J.M. Adam -Université de Grenoble Alpes -Grenoble

Objectif

Se familiariser avec les différentes

sortes de problèmes de plus court chemin

Savoir quel algorithme peut être

appliqué efficacement pour quel type de problème de plus courts chemins

2Heike Ripphausen-Lipa& Jean-Michel Adam

3

Sommaire

Introduction

Algorithmede Dijkstra

Algorithmede Bellman-Ford

Algorithmede Floyd-Warshall

Heike Ripphausen-Lipa& Jean-Michel Adam

Problème: trouverle cheminle plus court

AB

Trouverle plus courtcheminde A à B

0 5

Introduction

On considèreungrapheorientépondéré:

Graph G = (V,E)avec

Fonctionpoidsw: E -> R

(les poidsdes arcssontdes nombresréels)

Heike Ripphausen-Lipa& Jean-Michel Adam

6

Définition: Poidsd'unchemin

Le poidswd'uncheminpavec

p = (v 0 , v 1 , ... , v k )et (v i , v i+1 ) ɽE

Estdéfiniainsi:

i=1..k w(v i-1 , v i

Heike Ripphausen-Lipa& Jean-Michel Adam

7

Definition: poidsdu cheminle

plus court Le poids du chemin le plus court į(u,v)entre deux sommetsuet vestdéfiniainsi: min { w(p): pestuncheminde uà v dansG }, si uncheminexiste

į(u,v)=

, sinon

Heike Ripphausen-Lipa& Jean-Michel Adam

8

Idée de base pour trouver le chemin le

plus court De nombreux algorithmes de calcul de plus court chemin utilisent la propriétesuivante : Les sous-chemins des chemins les plus courts sont eux-mêmes les chemins les plus courts!

Plus précisément:

si p =(v 0 , v 1 , ... , v k )est un chemin le plus court entre les sommets v 0 et v k alors pour iet j(le chemin p ij = (v i , v i+1 , ..., v j )est le chemin le plus court du sommet v i au sommet v j

Heike Ripphausen-Lipa& Jean-Michel Adam

9

Idée de base pour trouver le chemin le

plus court Nous nous concentrons sur le problème des chemins les plus courts d'une source unique, c'est-à-dire que l'on calcule les chemins les plus courts du sommet de départ svers tous les sommets v du graphe. Beaucoup d'algorithme de calcul de plus court chemin utilisent la technique de relaxation : A chaque sommet von associe un attribut distqui donne une borne supérieure de la distance du plus court chemin d'un sommet s(la source) au sommet v.

Heike Ripphausen-Lipa& Jean-Michel Adam

10

Relaxation

La méthode relaxationd'un arc(u,v)consiste à voir s i le chemin le plus court calculé jusqu'à vpeut être amélioré en prenant le chemin le plus court actuel de svers u, en lui ajoutant l'arc (u,v):

Heike Ripphausen-Lipa& Jean-Michel Adam

11 initialisation-Source-Unique // Initialisationd'unalgorithmede relaxation // pourla recherchedes plus courtschemins // depuisunesourceunique: le sommets initialisation-Source-Unique(G, s) pourtoutsommet v de G dist[v] VMAX // valeurréellemax pred[v] NIL fpour dist[s] 0

Heike Ripphausen-Lipa& Jean-Michel Adam

12

Relax(u,v,w)

Relax(u, v, w)

// arc(u,v), w(u,v) estle poidsde l'arc sidist[v] > dist[u] + w(u,v) alors dist [v] dist[u] + w(u,v) pred[v] u fsi

Heike Ripphausen-Lipa& Jean-Michel Adam

Algorithme de Dijkstra

(publication 1959) 14

Algorithme de Dijkstra

L'Algorithme de Dijkstra résout le problème

des chemins les plus courts depuis une source unique, le sommet s.

L'Algorithme de Dijkstrane fonctionne que

pour des poids positifs.

Il fonctionne de manière similaire au

parcours en largeur, mais au lieu d'utiliser une file, il utilise une file prioritaire.

Heike Ripphausen-Lipa& Jean-Michel Adam

15

Algorithme de Dijkstra

L'algorithme de Dijkstra gère un ensemble (virtuel) S qui contient tous les sommets pour lesquels les distances les plus courtes depuis s sont déjà calculées.

Etapepar étape, le sommetude Sdontla valeur

distestminimale, estsélectionéet tousles arcs u,v incidentsà u sontrelaxés

Pourgérerl'ensembleS, des sommetsdontla

distanceminimale depuiss n'apasencoreété déterminée , on utilisela fileprioritaireQ.

Heike Ripphausen-Lipa& Jean-Michel Adam

16

Algorithme de Dijkstra

Dijkstra(G, w, s)

initialisation-Source-Unique(G, s)

S Ø; // tous les sommets atteints depuis s

Q tous les sommets // tous les sommets dans Q

tantque u Extraire-Min(Q) // sommet dont distminimale

S S.ajouter(u)

pourtout sommet v adjacent à u

Relax(u,v,w);

fpour ftq

Remarque: l'ensemblede sommetsS n'est

pas vraimentutile; ilestintroduitpour mieuxillustrerl'algorithme.

Heike Ripphausen-Lipa& Jean-Michel Adam

17 sa bc d e 2 1 33
1 51
2 i

Valeurde dist: i

Vide : VMAX

0 sabcde Remarque : Q estordonnéeselonles valeurscroisantesde dist

Algorithme de Dijkstra

File prioritaireQ

Heike Ripphausen-Lipa& Jean-Michel Adam

18 sa bc d e 2 1 33
1 51
2 0 bacde

File prioritaireQ

12

Les sommetsde S sontcolorésen noir

Algorithme de Dijkstra

Heike Ripphausen-Lipa& Jean-Michel Adam

19 sa bc d e 2 1 33
1 51
2 0 adce12 2

Algorithme de Dijkstra

File prioritaireQ

Heike Ripphausen-Lipa& Jean-Michel Adam

20 sa bc d e 2 1 33
1 51
2 0 12 252
dce

Algorithme de Dijkstra

File prioritaireQ

Heike Ripphausen-Lipa& Jean-Michel Adam

2 21
sa bc d e 2 1 33
quotesdbs_dbs45.pdfusesText_45

[PDF] algorithme de ford plus long chemin PDF Cours,Exercices ,Examens

[PDF] Algorithme de héron Terminale Mathématiques

[PDF] Algorithme de mathématiques 2nde Mathématiques

[PDF] Algorithme de maths 1ère Mathématiques

[PDF] Algorithme de maths 2nde Mathématiques

[PDF] Algorithme de mesure d'angle 1ère Mathématiques

[PDF] Algorithme de niveau Seconde 2nde Mathématiques

[PDF] algorithme de parcours en largeur PDF Cours,Exercices ,Examens

[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens

[PDF] ALGORITHME DE PILE OU FACE svp essayer de me faire comprendre cette algorithme 2nde Mathématiques

[PDF] Algorithme de Pythagore 2nde Mathématiques

[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques

[PDF] algorithme de recherche dextremum 2nde Mathématiques

[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens

[PDF] algorithme de recherche dichotomique PDF Cours,Exercices ,Examens