Ce travail pratique est organisé en plusieurs parties traitant la notion de recherche de plus court chemin dans un graphe. Il faudra implémenter les algorithmes de Floyd et de Dijkstra que vous avez vus en cours. Vous appliquerez ces algorithmes sur un graphe représentant un certain nombre de lignes ferroviaires suisses. Finalement, une partie graphique vous sera demandée pour rendre le travail un peu plus ludique.
Dans cette deuxième partie, vous aurez besoin des structures de données que vous avez implémenté ces dernières semaines: la liste et file d’adjacence, ainsi que la file de priorité.
L’algorithme de Dijkstra permet de déterminer le plus court chemin entre deux points d’un graphe: le sommet de départ et le sommet d’arrivée.
Dans cette section nous allons décrire l’algorithme en général, puis voir comment l’implémenter (lisez donc toute la section).
Il s’agit d’un algorithme qui améliore itérativement le calcul de la distance entre les sommets d’un graphe. Nous avons en premier lieu une étape d’initialisation:
La boucle de mise à jour des distances se passe comme suit:
L’algorithme le plus efficace (et également le plus simple) pour trouver le plus cours chemin entre un sommet de départ et tous les autres sommets d’un graphe utilise une file de priorité min.
Le pseudo-code est donné par
void dijkstra(graph g, int src, int num, int dist[num], int prev[num]) {
[src] = 0; // all other distances are INT_MAX
dist[src] = -1; // previous node is undefined
prev
(q, (src, 0));
queue_init
while (!queue_is_empty(q)) {
= queue_pop(q);
p for v in the neighborhood_of(g, p) {
= dist[p] + weight(g, p, v);
d_new if (d_new < dist[v]) {
[v] = d_new;
dist[v] = p;
prev(q, (v, d_new));
queue_push}
}
}
}
Il faut noter que la priorité est donnée par la distance totale
depuis le sommet de départ. La distance entre src
et tous
les autres sommets est dans le tableau dist
et le parcours
entre src
et un sommet v
, est obtenu à l’aide
du tableau prev
en suivant les indices en partant de
prev[v]
.
Cet algorithme ne fonctionne que pour les arêtes dont les poids sont positifs. Grâce à cette propriété, il est possible d’ajouter plusieurs fois le même sommet dans la file de priorité (c’est même normal que cela se produise).
L’algorithme de Floyd (ou Floyd–Warshal) est un algorithme qui sert à trouver les plus courts chemins entre toute paire de sommets d’un graphe.
Dans cette section nous allons d’abord décrire l’algorithme puis voir son implémentation.
Considérons un graphe avec \(N\)
sommets, numérotés de 0 à \(N-1\). Soit
la fonction shortest_path(i,j,k)
la fonction retournant le
plus court chemin entre le sommet i
et le sommet
j
en utilisant uniquement les sommets
0, ..., k-1
sommets intermédiaires. En supposant cette
fonction connue, nous voulons trouver le plus cours chemin en utilisant
les sommet 0
à N-1
. Pour chaque
shortest_path(i, j, k)
nous avons deux possibilités:
k-1
(il ne passe que par les
sommets 0
à k-2
).k-1
: d’abord de i
à
k-1
puis de k-1
à j
.Dans le premier cas, nous savons que le plus court chemin est défini
par shortest_path(i,j,k-1)
. Dans ce second cas, le chemin
serait la réunion des chemins de i
à k
, puis
de k
à j
. Ce chemin serait donc la somme des
chemins shortest_path(i, k, k-1)
et
shortest_path(k,j,k-1)
.
De la définition de la fonction shortest_path(i,j,k)
, on
peut déduire que shortest_path(i,j,0)
est donné par
(i,j,0)=w(i,j), shortest_path
où w(i,j)
est le poids de l’arrête entre les sommets
i
et j
.
Finalement, on peut définir le plus cours chemin récursivement
(i,j,k) = min(shortest_path(i,j,k-1),
shortest_path(i,k,k-1) + shortest_path(k,j,k-1)). shortest_path
L’algorithme de Floyd s’implémente à l’aide de la matrice d’adjacence. Il est décrit en pseudo-code comme
void floyd_warshall(int num, int dist[num][num], int next[num][num]) {
// init dist with INT_MAX
// init next with -1
for each edge (i, j) {
[i][j] = w(i, j) // The weight of the edge (i, j)
dist[i][j] = j
next}
for each vertex j {
[j][j] = 0
dist[j][j] = j
next}
for (int k = 0; k < num; ++k) { // standard Floyd-Warshall implementation
for (int i = 0; i < num; ++i) {
for (int j = 0; j < num; ++j) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
[i][j] = dist[i][k] + dist[k][j]
dist[i][j] = next[i][k]
next}
}
}
}
}
Pour retrouver le chemin il faut simplement suivre les indices dans
la matrice next
de la façon suivante
void get_path(int i, int j, int num, int next[num][num], vector *path) {
if next[i][j] is negative {
return
}
(path, i);
vector_pushwhile (i != j) {
= next[i][j];
i (path, i);
vector_push}
}
Afin de tester le code, vérifier que si vous chercher les temps de parcours entre les villes:
Geneve; Sion
Andermatt; Coire
Schaffouse; Lausanne
Lucerne; Delemont
Coire; Geneve
Bale; Bellinzone
Andermatt; Geneve
Lausanne; Delemont
Neuchatel; Bellinzone
Bellinzone; Geneve
Sion; Bale
Lausanne; Geneve
St.-Moritz; Geneve
Sion; Schaffouse
St.-Gall; Lausanne
Neuchatel; Andermatt
Sion; Neuchatel
Bale; Geneve
Geneve; Bale
Berne; Bellinzone
on obtient:
101 100 188 107 271 205 263 89 257 316
190 34 387 255 212 227 107 157 157 215
Puis les chemins entre les villes
Geneve; Sion
Andermatt; Coire
Schaffouse; Lausanne
Lucerne; Delemont
Coire; Geneve
Bale; Bellinzone
Andermatt; Geneve
LausanneDelemont
Neuchatel; Bellinzone
Bellinzone; Geneve
Sion; Bale
Lausanne; Geneve
St.-Moritz; Geneve
Sion; Schaffouse
St.-Gall; Lausanne
Neuchatel; Andermatt
Sion; Neuchatel
Bale; Geneve
Geneve; Bale
Berne; Bellinzone
sont donnés par
[Geneve:Lausanne:Sion]
[Andermatt:Coire]
[Schaffouse:Zurich:Berne:Lausanne]
[Lucerne:Bale:Delemont]
[Coire:Zurich:Berne:Lausanne:Geneve]
[Bale:Lucerne:Bellinzone]
[Andermatt:Sion:Lausanne:Geneve]
[Lausanne:Neuchatel:Delemont]
[Neuchatel:Berne:Lucerne:Bellinzone]
[Bellinzone:Lucerne:Berne:Lausanne:Geneve]
[Sion:Lausanne:Neuchatel:Delemont:Bale]
[Lausanne:Geneve]
[St.-Moritz:Coire:Zurich:Berne:Lausanne:Geneve]
[Sion:Lausanne:Berne:Zurich:Schaffouse]
[St.-Gall:Zurich:Berne:Lausanne]
[Neuchatel:Berne:Lucerne:Andermatt]
[Sion:Lausanne:Neuchatel]
[Bale:Delemont:Neuchatel:Lausanne:Geneve]
[Geneve:Lausanne:Neuchatel:Delemont:Bale]
[Berne:Lucerne:Bellinzone]
Sur Cyberlearn, vous trouverez un squelette de fichier pour avoir une application complète de recherche de chemin. Il faudra l’adapter à votre code (pas changer le format de sortie par contre) pour pouvoir l’exécuter avec vos différents algorithmes de recherche de plus court chemin et de temps de parcours.
Cela veut dire qu’il n’y a pas de chemin entre le sommet de départ et celui d’arrivée.↩︎