Programme

Nous avons créé et écrit un programme en Java capable de créer un graphe et de résoudre l’algorithme de Dijkstra sur ce dernier.
Tout d’abord quelque précision sur Java. Java est un langage de programmation orienté objet présenté en 1995. Depuis 2009 le langage Java appartient à la société Oracle. La particularité et l’objectif central de Java est que les logiciels écrit dans ce langage doivent être très facilement portable sur les différents systèmes d’exploitation (UNIX, Windows, Mac OS ou Linux) avec peu ou pas de modifications

 

Le programme est constitué de 5 Classes

Vertex.java: Cette classe définit un sommet. Ce sommet est défini par un id et un nom. Il y a ensuite le constructeur Vertex() qui crée l’objet Vertex (donc crée un sommet) à partir des attributs cité précédemment (id et name). La méthode getId() permet de récupérer l’id du Vertex en appelant la méthode. La méthode getName() fonctionne sur le même principe que getId() mais permet de récupérer le nom du Vertex. Les 3 autres méthodes sont juste des redéfinitions de méthode de base de Java : hashcode(), equals() (permet de voir si un objet et égal à un autre) et toString() (sert à l’affichage de l’objet dans la console).

Edge.java: Cette classe définit un arc. Cet arc est défini par un id, un sommet source, un sommet destination et un poids. Le constructeur Edge() crée l’objet Edge (donc crée un arc) à partir des attributs cité précédemment. Les getters (les méthodes get) permettent de récupérer quand on le veut différents attributs : getId() récupère l’id de l’arc, getSource() récupère le sommet source de l’arc, getDestination() récupère le sommet destination de l’arc et getWeight() récupère le poids de l’arc. La dernière méthode et une réécriture de la méthode toString().

Graph.java: Cette classe défini un graphe. Le graphe possède comme attributs 2 List : une List de Vertex (sommet) et une List de Edge (arc). Le constructeur Graph() crée donc l’objet Graph à partir des deux attributs cité précédemment. La méthode getVertexes() permet de récupérer la List des sommets à tous moments, la méthode getEdges() fait la même choses mais pour les arcs. La méthode afficher() permet d’afficher le graph sous forme de texte dans la console. Enfin la méthode getDistance() prend en paramètre 2 sommets et permet de connaître la distance/poids entre les sommets.

Le résultat de la méthode afficher() dans la console apparaît de cette manière : sommet source — distance/poids de l’arc — sommet destination.

DijkstraAlgorithm.java: Cette classe est la classe qui va réaliser l’algorithme. Elle prend en attribut un graphe de type Graph. Elle prend aussi en attribut 2 List de sommets appelé OPEN et CLOSE, indiquant les sommets disponibles (Open) et les sommets déjà visité (Close). Une Map ou chaque vertex est lié à son parent. Et enfin une autre Map ou chaque Vertex est associé à la distance qu’il y a entre lui et le sommet d’origine. Le constructeur lui prend en paramètre un graph et le définit en tant qu’attribut car c’est sur le graph que va s’exécuter la résolution d’algorithme.
La méthode init(Vertex sourceNode) prend en paramètre le sommet source de l’algorithme. Cette méthode initialise toutes les List et Map de l’algorithme.
La méthode displayCurrentState() se contente juste d’afficher les List et les Map dans l’état actuel de l’algorithme.
La méthode getNeighbors() retourne tous les voisins du sommet donné en paramètre.
La méthode getNodesWithLowestDistance(Set<Vertex> nodes) retourne à partir d’une list le sommet ayant le distance la plus courte parmis la List.
La méthode getPath(Vertex target) retourne le chemin allant du sommet « target » au sommet source
Et enfin la méthode la plus importante et la méthode execute(Vertex sourceNode). Elle fait appel à quelques-unes des méthodes précédentes et permet de résoudre l’algorithme de Dijkstra.

Main: Dans un premier temps le programme va commencer par crée les sommets (Vertex) un par un. Ex : Vertex v1 = new Vertex(1, « v1 ») ; Le premier paramètre est l’id et le deuxième est le nom du sommet.
Une fois que le programme a crée les sommets, il peut alors créer les arcs. Ex : Edge a1 = new Edge(1, v1, v2, 3) ; le premier entier est l’id de l’arc, puis il y a le sommet de départ v1, le sommet destinataire v2 et enfin le poids de l’arc.
Enfin le programme va créer la Liste de sommets et la Liste des arcs qui vont être remplis par les sommets
Pour finir le programme va créer un Graph en lui donnant les Listes de sommets et d’arcs en paramètres.

Exécution du programme:

Dans un premier temps le programme construit un graphe et afficher toutes ses arrêtes dans la console de l’utilisateur.

(Sommet 1 — distance — sommet 2)

Après avoir initialiser l’algorithme, le programme va l’exécuter et afficher toutes les étapes de son déroulement

Une fois l’exécution de l’algorithme terminé, le programme va afficher les résultats