Un graphe orienté est défini par l'ensemble de ses sommets ou nœuds , reliés entre eux par des flèches appelés arcs indiquant le sens de parcours dans le graphe.
On convient de numéroter les n sommets de 1 à n, en suivant par exemple l'ordre alphabétique: "A" numéroté 1, "B" numéroté 2, etc...
Le graphe est pondéré si,  à chaque arc d'origine le sommet de numéro x et d'extrémité le sommet de numéro y, est associée une valeur réelle δ(x,y) appelée distance de x à y.   On notera  [x, y, δ(x,y)] l'arc pondéré ainsi défini.  

Exemple (source wikipedia):
Le graphe représenté ci-dessous est un graphe orienté, de sommets "A","B",...,"J" et pondéré, dont les distances sont les valeurs réelles positives encadrées.
Par exemple, la distance du sommet "A" au sommet "B" est δ(1,2)=10, mais il n'existe pas d'arc reliant le sommet "B" au sommet "A".
 

1° Représenter le graphe précédent par une structure de type G:=[ liste des sommets, liste des arcs pondérés [x, y, δ(x,y)] ].

2° Matrice des distances
On convient de représenter un graphe orienté pondéré ayant n sommets par une matrice M carrée n x n définie par:
M[x,y] = 0 si x = y , M[x,y] = δ(x,y) si  x≠y et il existe un arc d'origine le sommet de numéro x et d'extrémité le sommet de numéro y, et M[x,y] =∞sinon.

Ecrire une procédure matdist( G :: list) qui, à partir d'une liste G définie comme au 1° représentant la structure d'un graphe orienté pondéré, construit la matrice M des distances associée.

Exemple: pour le graphe précédent, on obtient donc le résultat  

(1)

3° L'algorithme de Dijkstra permet de trouver le plus court chemin pour relier le sommet de numéro dep au sommet de numéro arv.
Un sommet de départ dep étant fixé, cet algorithme construit progressivement un ensemble de sommets pour lesquels on connaît un plus court chemin depuis dep.
A chaque étape, on choisit un sommet dont la distance à  dep est minimale parmi ceux qui n’ont pas encore été choisis.On utilisera un ensemble c des sommets à choisir successivement et deux tableaux d et pred  des distances et des prédécesseurs.

procédure Dijkstra( M (matrice des distances) , dep , arv )

Initialisation:
 
c ← {dep} ; d[dep] ← 0

pour tout sommet k faire
    si k≠ dep alors d[k]← M[dep,k] ; pred[k]←dep fin si
fin pour

Construction de l'ensemble c:

Programmer cet algorithme en langage Maple par une procédure Dijkstra( M :: matrix, dep :: posint, arv :: posint), M étant la matrice des distances associée au graphe (définie dans la question 2°). 

Exemple: 

>

(2)

>

(3)

>

(4)

Corrigé: Algorithme de Dijkstra 

1°





 

(5)

2°  

(6)

3°  Algorithme de Dijkstra:
 

>

>

(7)

>

(8)

>

(9)