README.md

# Plus courts chemins

<!-- Introduction -->
Pour ce projet nous allons nous miser sur la performance de nos implémentations d'algorithmes de plus courts chemins.   
L'algorithme de Dijkstra calcule les chemins les plus courts depuis un nœud donné appelé source vers tous les autres nœuds d'un graphe. Il produit un arbre de chemin le plus court enraciné dans la source. Cet algorithme ne fonctionne que pour des longueurs non négatives que nous allons evidemment nous en servir ici.   
Pour la mise en oeuvre, nous utiliserons des générateurs de graphe de taille **N** donnée que l'API de Graphstream nous met déja à disposition.  
Pour citer, il existe les générateurs suivants:
*  **Banana Tree**
*   **Barabasi-Albert**
*   **Chvatal**
*   **etc ...**   
Chacun d'entre eux a ses spécificités mais nous allons ici nous intéresser au **[RandomGenerator](https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/generator/RandomGenerator.html)**.
### 1.  RandomGenerator  
Ce générateur crée des graphes aléatoires de n'importe quelle taille. Les liens de ces graphiques sont créés en fonction d'un seuil. Si la distance euclidienne entre deux nœuds est inférieure à un seuil donné, alors un lien est créé entre ces 2 nœuds. L'appel de `begin()` place un nœud unique dans le graphique, puis `nextEvents()` ajoute un nouveau nœud à chaque appel et connecte ce nœud à ses voisins en fonction de la distance planaire euclidienne seuil.

Ce générateur a la possibilité d'ajouter des valeurs numériques choisies au hasard sur des attributs arbitraires sur les bords ou les nœuds du graphique, et de choisir au hasard une direction pour les bords.

Une liste d'attributs peut être donnée pour les nœuds et les arêtes. Dans ce cas, chaque nouveau nœud ou bord ajouté aura cet attribut et la valeur sera un nombre choisi au hasard. La plage dans laquelle ces nombres sont choisis peut être spécifiée.

Par défaut, les bords ne sont pas orientés. Il est possible de demander l'orientation, auquel cas la direction est choisie au hasard.

Concernant la compléxité de ce générateur, chaque appel à `nextEvents()` au maximum, k opérations sont exécutées avec k le degré moyen.

Exemple avec code:  
```Java
 Graph graph = new SingleGraph("Random");
     Generator gen = new RandomGenerator(2);
     gen.addSink(graph);
     gen.begin();
     for(int i=0; i<100; i++)
         gen.nextEvents();
     gen.end();
     graph.display();
```
### 2.   Description de l'algorithme naive de Dijkstra 
C'est à dire qu'à partir d'un seul point, on cherche à trouver le chemin le plus court vers un autre point, disons X.   
#### Parcours en largeur
Sa mise en oeuvre se base sur une recherche modifiée en largeur. La recherche en largeur d'abord ([BFS](https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur)) est un algorithme de traversée de graphe qui fonctionne en explorant d'abord tous les nœuds voisins, avant de passer au niveau suivant de voisins (voisins de voisins).
#### Fil d'attente prioritaire
L'une des modifications de l'algorithme de Dijkstra sur la recherche en largeur d'abord est son utilisation d'une file d'attente prioritaire au lieu d'une file d'attente normale. Avec une file d'attente prioritaire, chaque noeud ajoutée à la file d'attente a une «priorité» et s'insérera en conséquence dans la file d'attente en fonction de son niveau de priorité.
#### Etapes de l'algorithme 
1.  Initialiser le noeud source avec une distance de 0 puisque nous commençons à partir de celui-ci.
2.  Initialiser tous les autres nœuds avec une distance infinie.
3.  Démarrer la boucle de file d'attente après y avoir inséré notre nœud source.  

Pour chaque voisin de notre nœud,  on calcul la distance provisoire entre la distance du nœud actuel et la distance à son voisin.  
  
Si la distance provisoire est inférieure à la distance du voisin, définissez la distance de ce nœud voisin sur la distance provisoire et mettez-la en file d'attente avec cette distance comme priorité.
  
Continuez à travers la file d'attente prioritaire jusqu'à ce que nous ayons calculé le chemin le plus court de tous les nœuds vers la source

En option, nous pouvons fournir un nœud cible et dès que ce nœud est retiré de la file d'attente, nous pouvons arrêter notre recherche

####Complexité
La compléxité depend en effet de l'implémenetation des fils d'attente prioritaires.
pour une simple liste sa compléxité sera de **O(n²)** alors que pour une liste triée elle sera de **O(nm)**.
### 3.   Description de l'algorithme Dijkstra de Graphstream
Graphstream nous met déja à disposition des algorithmes pour traiter nos graphes et a aussi implémenter sa version de Dijkstra.   En effet, cette implémentation utilise en interne Fibonacci Heap, une structure de données qui la rend plus rapide pour les gros graphiques.  
Lors d'un appelle de la méthode `compute()`, l'algorithme calcul non seulement le plus court chemin d'un noeud source vers tout les autres mais aussi permet de prendre également en compte "les longeurs des noeuds" ainsi que d'autres fonctionnalités.  
Voici un exemple de code:

```java
 Graph graph = ...;
 Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.edge, "result", "length");
 // calcul le chemin le plus court dans le graphe à partire de A vers tout les autres noeuds
 dijkstra.init(graph);
 dijkstra.setSource(graph.getNode("A"));
 dijkstra.compute();
 // Affiche le plus court chemin entre les noeuds A et B
 System.out.println(dijkstra.getPath(graph.getNode("B"));
 
```

### 4.   Comparaison avec l'algorithme de Graphstream
  Complexité
  Tem  
### 5.  Description des tests
Pour la procédure de test nous allons tour à tour mesurer le temps d'execution de ces deux algorithme en multipliant par pas de un le nombre de noeuds.
On va debuter avec un échantillon de 500 noeuds. A la fin on mesure le temps pris par le code a s'executer et on stockera nos resultats dans un fichier **test.dat**
```java
....
int i = 1, len = 500;
while (len < 10) {
    debut = System.currentTimeMillis();
    naiveDjikistra.compute(); // execution de notre algorithme
    fin = System.currentTimeMillis();
    total = fin - debut;
    writer.write(String.format("%6d%8f", len, total)); // écriture dans test.dat
    i++;
    len *= i;
}

```
### 6.  Interprétation
Nous allons interpéter le résultat de nos tests en affichant une courbe à l'aide d'outils comme `gnuplot`.
 
![Courbe de temps d'éxecution de chaques algorithmes]("screenshoots/courbe.png")  

On constate que plus la taille de notre graphe augmente plus l'algorithme de Djikistra de graphstream prends du temps à s'exécuter.   
Notre implémentation naive de Dijkstra est en effet que l'ajout de quelques actions à l'algorithme de parcours en largeur
de graphes qui prends **O(M + N)**. Néanmoins, à cela s'ajoute aussi la recherche de l'élèment à priorité minimale qui est de **O(N)** en utilisant un simple algorithme de parcours.  
De l'autre côté, l'algorithme mise à disposition par GraphStream prends **O(m + nlogn)** à l'appelle de `compute()`, cela est dûe au fait d'implémentations d'autres méthodes à la notre.