L'objet de ce TP est de comprendre et d'implémenter l'algorithme de Dijkstra (du mathématicien et informaticien néerlandais Edsger Dijkstra, 1930-2002, lauréat du prix Turing en 1972) permettant de déterminer le plus court chemin dans un graphe. On donnera ensuite une application de l'algorithme pour redimensionner une image de manière intelligente .

Introduction

Un graphe est un ensemble de points appelés noeuds et de segments appelés arcs reliant ces noeuds par paires. Si ces segments sont des èches, on dit que le graphe est orienté. On se contentera ici de traiter le cas de graphes orientés. Ces arcs peuvent être pondérés pour représenter une distance entre noeuds, un coût, etc. Un graphe peut servir à représenter un réseau informatique, un réseau de transports en commun, ou même une image, comme on le verra en application.

On définit un chemin dans un graphe orienté pondéré comme une suite de noeuds reliés deux à deux par des arcs, et la longueur d'un chemin comme la somme des longueurs des arcs de cette suite.

L'algorithme de Dijkstra permet de résoudre le problème suivant : étant donné un graphe orienté pondéré, un noeud de départ et un noeud d'arrivée, trouver un chemin de longueur minimal allant du noeud départ au noeud d'arrivée.

2 Pseudo-algorithme

On donne ci-dessous l'algorithme de Dijkstra en pseudo-code permettant de déterminer la distance minimale d'un noeud de départ à un noeud d'arrivée.

Si S et A dénotent respectivement le nombre de sommets et le nombre d'arcs du graphe, alors l'algorithme de Dijkstra a un coût en temps en O((S + A) ∗ ln(S)), en utilisant des structures de données appropriées pour représenter le graphe et récupérer le noeud non visité de distance minimale

Q1 Appliquer l'algorithme de Dijkstra à la main  au graphe ci-dessous.

Q2 Proposer une modication de l'algorithme de Dijkstra pour que celui-ci retourne également un chemin de distance minimale reliant le noeud de départ au noeud d'arrivée.