Fiche TP 2

L'objet de ce TP est de comprendre et d'implémenter l'algorithme de Dijkstra (en utilisant le langage de programmation que vous voulez) permettant de déterminer le plus court chemin dans un graphe.

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 flè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.

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