Programmer l'algorithme de Dijkstra

Il s'agit de calculer les plus courts chemins dans un graphe orienté valué d'un sommet r à tous les autres. Les sommets du graphe seront identifiés par des chaînes de caractères. Les longueurs des arcs seront des entiers positifs et ne seront pas des distances euclidiennes.
On pourra pour simplifier supposer que r est racine du graphe, mais il serait mieux de prévoir le cas où r n'est pas racine, c'est-à-dire où certains sommets ne peuvent pas être atteints depuis r.
Les données du problème seront fournis par un fichier. Vous pouvez trouver ici un fichier source pour un exemple que vous avez peut-être rencontré dans le cours d'algorihtmique. Dans le fichier, on trouve successivement :

le nombre de sommets ;
la liste des sommets, avec une ligne pour chaque sommet, et sur chaque ligne le nom du sommet et ses coordonnées entières dans un plan ;
le nom du sommet à partir duquel on veut calculer les plus courts chemins ;
la liste des arcs et leur longueur (origine extrémité longueur).

La sortie du programme, pour le fichier donné en exemple, peut être :

soit obtenue sur la sortie standard, auquel cas la réponse du programme pourrait être, pour notre exemple :

Les chemins et les distance depuis Paris  sont :
Pour Paris :  Paris, distance 0
Pour Hambourg :  Paris Amsterdam Hambourg, distance 5
Pour Amsterdam :  Paris Amsterdam, distance 3
Pour Londres :  Paris Amsterdam Londres, distance 4
Pour Stockholm :  Paris Amsterdam Hambourg Stockholm, distance 6
Pour Berlin :  Paris Amsterdam Hambourg Berlin, distance 6
Pour Edimbourg :  Paris Amsterdam Londres Edimbourg, distance 6
Pour Oslo :  Paris Amsterdam Hambourg Stockholm Oslo, distance 8
Pour Rana :  Paris Amsterdam Hambourg Stockholm Oslo Rana, distance 10

soit obtenue sous une forme graphique, avec par exemple une fenêtre surgissante telle que celle représentée ci-dessous :

À côté de chaque arc apparaît la longueur de l'arc, à côté de chaque sommet apparaît la distance depuis Paris, les arcs plus gras sont ceux de l'arborescence, l'extrémité d'un arc est rouge (il est difficile de faire des flèches).
Nous vous laissons concevoir vous-même le logiciel correspondant.

Corrigé :

Voici une possibilité :

La classe Sommet
La classe Arc
La classe Arborescence
L'interface nommée Graphique
La classe PanneauDessin
Une classe pour une méthode main avec le résultat sur la sortie standard
Une classe pour une méthode main, version représentation graphique