TIPE
M AT H S A P P L I Q U E E S E T I N FO R M AT I Q U E P R AT I Q U E
A la recherche du
plus court chemin
Présenté Par : ZAKARIA BHEDDAR
Plan de la
présentation
Sommaire:
-Motivation
-Problématique
-Initialisation à la théorie des graphes
-Conversion d’une carte routiere ou
geographique en un graphe et ses
representations
-Les algos et méthodes fréquentes pour la
recherche du plus court chemin
-Partie programmation et applications
-Optimisation
-Conclusion
ZAKARIA BHEDDAR MPSI 2 | LYDEX
PARTIE 1
Motivation pour le choix du sujet
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Joseph Joubert
Tout ce qui est exact est court.
ZAKARIA BHEDDAR
Figure - 1 Figure - 2
• Figure 1 : un système de navigation gps sur téléphone
• Figure 2 : une personne énervée du temps qui a gaspillé en tram
• C/C : le développement d’un système de navigation est néccessaire et va
faciliter le déplacement des citoyens d’une ville.
ZAKARIA BHEDDAR
Figure - 3 Figure - 4
• Figure 3 : l’une des fréquentes moyens de transports que les citoyens utilisent
• Figure 4 : la livraison rapide des produits à domicile
• C/C : la néccessité de ce système pour ne pas gaspiller le temps et aussi pour
diminuer le coût de gazoline.
ZAKARIA BHEDDAR
Le temps est si précieux qu’il faudrait bien le
gérer,c’est pour cela chaque citoyen doit se
déplacer d’une manière courte et efficace
dans une ville pour ne pas gaspiller son
temps afin d’accomplir le maximum de
tâches qu’il pourrait faire.
En guise d’exemple , les Gps nous aidents à
satisfaire cette nécessité et ont plusieurs
applications dans notre vie quotidienne : le
déplacement des ambulances / des ubers /
des taxis / la livraison rapide …
ZAKARIA BHEDDAR MPSI 2 | LYDEX
PARTIE 2
Problématique
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
La question qui se pose :
Comment peut-on résoudre ce problème et
trouver l’itinéraire le plus court vers une
destination précise?
ZAKARIA BHEDDAR
PARTIE 3
Initialisation à la théorie des graphes
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Figure - 1 Figure - 2
• Figure 1/2 : le problème des sept ponts de Königsberg
ZAKARIA BHEDDAR
L’histoire de la théorie des graphes débute peut-être avec les travaux d’Euler au XVIIIe siècle et trouve son
origine dans l’étude de certains problèmes, tels que celui des ponts de Königsberg (les habitants de Königsberg
se demandaient s’il était possible, en partant d’un quartier quelconque de la ville, de traverser tous les ponts
sans passer deux fois par le même et de revenir à leur point de départ), la marche du cavalier sur l’échiquier ou
le problème de coloriage de cartes.
La théorie des graphes s’est alors développée dans diverses disciplines telles que la chimie, la biologie, les
sciences sociales. Depuis le début du XXe siècle, elle constitue une branche à part entière des mathématiques,
grâce aux travaux de König, Menger, Cayley puis de Berge et d’Erdös.
De manière générale, un graphe permet de représenter la structure, les connexions d’un ensemble complexe en
exprimant les relations entre ses éléments : réseau de communication, réseaux routiers, interaction de diverses
espèces animales, circuits électriques,. . .
Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété de
problèmes en se ramenant à l’étude de sommets et d’arcs. Les derniers travaux en théorie des graphes sont
souvent effectués par des informaticiens, du fait de l’importance qu’y revêt l’aspect algorithmique.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Il est donc légitime de se demander:
C’est quoi un graphe ?
ZAKARIA BHEDDAR
Notions fondamentales sur les graphes
- Un graphe orienté G = (X,U) est déterminé par la donnée :
n
• D’un ensemble X = ai non vide et fini dont les éléments sont appelés sommets ou
i =1
nœuds. Si 𝑛 = |𝑋| est leur nombre, on dira que 𝐺 est d’ordre 𝒏.
• D’un ensemble U X X dont les éléments sont des couples ordonnés de sommets
appelées arcs ou arêtes. On notera souvent |U| = m.
- Si 𝑢 = (𝑖,𝑗) est un arc de 𝐺, 𝑖 et 𝑗 sont les extrémités de 𝑢 et sont dites adjacentes. Si 𝑢 est
orienté de 𝑖 vers 𝑗, alors 𝑖 est l’extrémité initiale de 𝑢 et 𝑗 est l’extrémité terminale de 𝑢.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Notions fondamentales sur les graphes
-Exemple :
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Notions fondamentales sur les graphes
- Un graphe pondéré G = (X,U,w) est déterminé par la donnée :
n
• D’un ensemble X = ai non vide et fini dont les éléments sont appelés sommets ou
i =1
nœuds. Si 𝑛 = |𝑋| est leur nombre, on dira que 𝐺 est d’ordre 𝒏.
• D’un ensemble U X X dont les éléments sont des couples ordonnés de sommets
appelées arcs ou arêtes. On notera souvent |U| = m.
• w(u, v) est le poids de l’arête (u, v).
• Dans un graphe pondéré, le poids w(p) d’un chemin p est la somme des poids des
k −1
arêtes le long du chemin , tel que : w( p ) = w(a , a
i =1
i i +1 )
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Notions fondamentales sur les graphes
-Exemple :
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Dans la suite et la résolution du problème, on
s’intéressera aux :
graphes pondérés
ZAKARIA BHEDDAR
Exemple pour la représentation d’un réseau
routier de quelques villes en France:
ZAKARIA BHEDDAR
PARTIE 4
Conversion d’une carte routiere ou
geographique en un graphe et ses
representations
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Chaque sommet correspondera à une destination
dans la ville, et on reliera entre eux si c’était
possible par des arêtes, et le poids correspondera
au temps de parcours ou à la distance
Mais, comment peut-on stocker un graphe d’une
manière efficace ?
ZAKARIA BHEDDAR
Représentation d’un graphe:
NB : Comme l’indique l’illustration, on doit équilibrer entre les deux.
ZAKARIA BHEDDAR
Représentation d’un graphe:
• Aucune représentation n’est parfaite.
• Choix de la structure à adopter en fonction du graphe et l’algorithme.
• Trois structures très utilisées:
• Matrice d’incidence nœud-arc
• Matrice d’adjacence nœud-nœud
• Liste d’adjacence
ZAKARIA BHEDDAR
PARTIE 4
Les algos et méthodes fréquentes pour
la recherche du plus court chemin
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
C’est quoi le plus court chemin ?
ZAKARIA BHEDDAR
DEFINITION
• Le plus court chemin entre deux sommets s et t est défini comme le chemin de plus
faible poids reliant s et t.
• Notation mathématique :
p
(u, v) = { min{ w ( p ) : u
v} s’il existe un chemin entre u et v
sinon
ZAKARIA BHEDDAR MPSI 2 | LYDEX
LEMME
Tous les sous-chemins d’un plus court chemin sont
eux-mêmes des plus courts chemins.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Représentation machine
• Matrices d’adjacences,
• Pour des raisons de commodités: on suppose que les sommets sont numérotés
comme cela : 1, 2, 3,… ,|S|.
• On utilise une matrice W de type n x n qui représente les poids d’arc d’un graphe
G=(X,U,w) tel que |X|=n # à n sommets :
Si i = j
{
0
(i, j ) |1, n | wi , j = w( pi , j ) Si i j et (i , j ) U
2
Si i j et (i, j ) U
ZAKARIA BHEDDAR MPSI 2 | LYDEX
REMARQUES
• Les arcs de poids négatif sont autorisés mais on suppose qu’il n’y a aucun circuit de
longueur strictement négative.
• La sortie par les algorithms est une matrice n x n d11 d1n
• Notation de la matrice : D = ( di , j ) =
• d i , j est la longueur d’un plus court chemin reliant d n1
d nn le sommet i
au sommet j.
• Autrement dit, si l’on appelle (i, j ) la longeur de plus court chemin du sommet I
au sommet j alors d i , j = (i, j ) à la fin de l’exécution.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Algorithme Floyd-Warshall
• Cet algorithme décrit en 1959 par Bernard Roy détermine les distances des plus
courts chemins entre toutes les paires de sommets dans un graphe orienté et
pondéré en temps cubique en le nombre de sommets.
• Prend en entrée un graphe orienté et valué décrit par une matrice d’adjacence,
• C’est un exemple de programmation dynamique.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Présentation
k k
• On note W la matrice des W i, j .
0
• Pour k = 0 , W est la matrice d’adjacence par poids.
• Trouvons une relation de récurrence. On considère un chemin entre i et j de poids
minimal dont les sommets intermédiaires sont dans 1, 2,..., k . De deux l’une:
• Soit C n’emprunte pas le sommet k.
• Soit C emprunte exactement une fois le sommet k ( car les circuits sont de poids
positifs ou nuls ) et C est donc la concaténation de deux chemins Ci ,k et Ck , j
dont les sommets intermédiaires sont dans 1, 2,..., k − 1 . Par principe de sous-
optimalité, si C est optimal alors Ci ,k et Ck , j le sont aussi.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Algorithme :
Inconvénient: on crée une matrice à chaque iteration. Coûteux en mémoire.
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Algorithme amélioré:
• Avantage: il n’y a plus qu’une matrice modifiée à chaque iteration
• Complexité temporelle en ( n ) (triple boucle toujours parcourue)
3
• Complexité en mémoire de l’ordre du nbr de coefs , donc ( n )
2
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Exemple:
Considérons ce graphe:
8
1 2
7 2 2
4 1 3
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Matrice d’adjacence de ce graphe est:
0 3 7
8 0 2
A =
0
5 0 1
2 0
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Considérer le sommet 1:
u intermédia v [u,v] [u,x]+[x,v] coût
8 ire
2 [2,1]+[1,3] 3 2 8+∞ 2
1 2 2 [2,1]+[1,4] 4 ∞ 8+7 15
3 [3,1]+[1,2] 2 ∞ 5+3 8
7 2 2
3 [3,1]+[1,4] 4 1 5+7 1
4 1 3 4
4
[4,1]+[1,2]
[4,1]+[1,3]
2
3
∞
∞
2+3
2+∞
5
∞
0 3 7 0 3 7
8 0 2 8 0 2 15
A =
0 → A =
1
5 0 1 5 8 0 1
2 0 2 5 0
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Considérer le sommet 2:
u intermédia v [u,v] [u,x]+[x,v] coût
8 ire
1 [1,2]+[2,3] 3 ∞ 3+2 5
1 2 1 [1,2]+[2,4] 4 7 3+15 7
3 [3,2]+[2,1] 1 5 8+8 5
7 2 2
3 [3,2]+[2,4] 4 1 8+15 1
4 1 3 4
4
[4,2]+[2,1]
[4,2]+[2,3]
1
3
2
∞
5+8
5+2
2
7
0 3 7 0 3 5 7
8 0 2 15 8 0 2 15
A =
1 → A =
2
5 8 0 1 5 8 0 1
2 5 0
2 5 7 0
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Considérer le sommet 3:
u intermédia v [u,v] [u,x]+[x,v] coût
8 ire
1 [1,3]+[3,2] 2 3 5+8 3
1 2 1 [1,3]+[3,4] 4 7 5+1 6
2 [2,3]+[3,1] 1 8 2+5 7
7 2 2
2 [2,3]+[3,4] 4 15 2+1 3
4 1 3 4
4
[4,3]+[3,1]
[4,3]+[3,2]
1
2
2
5
1+5
7+8
2
5
0 3 5 7 0 3 5 6
8 0 2 15 7 0 2 3
A =
2 → A =
3
5 8 0 1 5 8 0 1
2
5 7 0 2 5 7 0
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Considérer le sommet 4:
u intermédia v [u,v] [u,x]+[x,v] coût
8 ire
1 [1,4]+[4,2] 2 3 6+5 3
1 2 1 [1,4]+[4,3] 3 5 6+7 5
2 [2,4]+[4,1] 1 7 3+2 5
7 2 2
2 [2,4]+[4,3] 3 2 3+7 2
4 1 3 3
3
[3,4]+[4,1]
[3,4]+[4,2]
1
2
5
8
1+2
1+5
3
6
0 3 5 6 0 3 5 6
7 0 2 3 5 0 2 3
A =
3 → A =
4
5 8 0 1 3 6 0 1
2
5 7 0 2 5 7 0
ZAKARIA BHEDDAR MPSI 2 | LYDEX
8
1 2
7 2 2
4 1 3
1 2 3 4
1 0 3 5 6 : Plus court chemin à partir du sommet 1
2 5 0 2 3 : Plus court chemin à partir du sommet 2
3 3 6 0 1 : Plus court chemin à partir du sommet 3
4 2 5 7 0 : Plus court chemin à partir du sommet 4
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Algorithme implémenté en python:
import math def FloydWarshal(self):
res = [Link]()
class Graphe(): n = len([Link])
def __init__(self, noeuds): for k in range(n):
[Link] = [Link]() for i in range(n):
for j in range(n):
def Afficher(self, res): res[i][j] = min(res[i][j], res[i][k]+res[k][j])
print("les chemins les plus courts allant de est : ") [Link](res)
n = len(res)
for i in range(n): # Test
print("les chemins les plus courts allant de ", i+1, " est : ") matriceAdj = [[0, 3, [Link], 7],
for j in range(n): [8, 0, 2, [Link]],
print(res[i][j], end=" ") [5, [Link], 0, 1],
print("") [2, [Link], [Link], 0],
]
g = Graphe(matriceAdj)
[Link]()
ZAKARIA BHEDDAR MPSI 2 | LYDEX
L’execution du code donnera:
ZAKARIA BHEDDAR MPSI 2 | LYDEX
PARTIE 5
Optimisation
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
L’utilisation de cet algorithme seul ne détermine
que la distance du trajet court qu’on doit suivre.
On doit trouver une solution qui permettra de
construire le chemin.
ZAKARIA BHEDDAR
Optimisation
• L’idée principale ici est d’utiliser une matrice (array 2D) qui gardera une trace du
prochain nœud à pointer si le chemin le plus court change pour une paire de
nœuds. Initialement, le chemin le plus court entre deux nœuds u et v est v (c’est le
bord direct de u -> v).
• Initialisation de la baie suivante
• Si le chemin existe entre deux nœuds alors Next[u][v] = v
• sinon nous définissons Next[u][v] = -1
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Optimisation
• Modification de l’algorithme Floyd Warshall
• Dans la condition if de l’algorithme de Floyd Warshall, nous ajouterons une
instruction Next[i][j] = Next[i][k]
• (cela signifie que nous avons trouvé le chemin le plus court entre i, j à travers un
nœud intermédiaire k) if(dis[i][j] > dis[i][k] + dis[k][j])
{
• Voici à quoi ressemblerait notre condition si
dis[i][j] = dis[i][k] + dis[k][j];
Next[i][j] = Next[i][k];
}
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Optimisation
• Pour construire un chemin à l’aide de ces nœuds, nous allons simplement
commencer à parcourir le nœud u tout en mettant à jour sa valeur à next[u][v]
jusqu’à ce que nous atteignions le nœud v .
path = [u]
while u != v:
u = Next[u][v]
[Link](u)
ZAKARIA BHEDDAR MPSI 2 | LYDEX
On peut modéliser cette approche en python à
l’aide des fonctions suivantes:
ZAKARIA BHEDDAR
import sys
INF = [Link]
def transformer_mat_adj_en_liste_distances(graph):
s = []
n = len(graph)
for i in range(n):
for j in range(n):
if i != j and graph[i][j] != INF:
[Link]([i+1,j+1,graph[i][j]])
return s
ZAKARIA BHEDDAR MPSI 2 | LYDEX
def floyd_warshall(graph):
source_vertices = [column[0] for column in graph]
destination_vertices = [column[1] for column in graph]
vertices = list(set(source_vertices) | set(destination_vertices))
distance = [[INF] * len(vertices) for i in range(len(vertices))]
next_vertices = [[0] * len(vertices) for i in range(len(vertices))]
for i in range(len(vertices)):
distance[i][i] = 0
for source, destination, weight in graph:
distance[source-1][destination-1] = weight
next_vertices[source-1][destination-1] = destination-1
for k in range(len(vertices)):
for i in range(len(vertices)):
for j in range(len(vertices)):
if distance[i][j] > distance[i][k] + distance[k][j]:
distance[i][j] = distance[i][k] + distance[k][j]
next_vertices[i][j] = next_vertices[i][k]
path_reconstruction(distance, next_vertices)
ZAKARIA BHEDDAR MPSI 2 | LYDEX
def path_reconstruction(dist, nxt):
print("Edge \t\t Distance \t Shortest Path")
for i in range(len(dist)):
for j in range(len(dist)):
if i != j:
path = [i]
while path[-1] != j:
[Link](nxt[path[-1]][j])
print("(%d, %d) \t\t %2d \t\t %s"
% (i + 1, j + 1, dist[i][j], ' - '.join(str(p + 1) for p in path)))
print()
def les_chemins_courts_possibles(graph):
return floyd_warshall(transformer_mat_adj_en_liste_distances(graph))
ZAKARIA BHEDDAR MPSI 2 | LYDEX
Simulation 8
1 2
• Pour le graphe précédent, on aura les résultats suivants : 7 2
2
4 1 3
1 2 3 4
1 0 3 5 6
2 5 0 2 3
3 3 6 0 1
4 2 5 7 0
ZAKARIA BHEDDAR MPSI 2 | LYDEX
PARTIE 5
Conclusion
A la recherche du plus court chemin
ZAKARIA BHEDDAR MPSI 2 | LYDEX
C’est difficile de construire manuellement un
graphe d’une ville.
Donc nous devons chercher une manière
automatique qui permettra de détecter les
routes et accomplir les tâches précédentes.
ZAKARIA BHEDDAR
Merci pour votre
attention
ZAKARIA BHEDDAR MPSI 2 | LYDEX