# TP 3 - Plus courts chemins

## 1. Charger et afficher ce graphe. Appliquer une feuille de style pour rendre l'affichage plus joli et ressemblant à une carte routière. De quelle ville s'agit-il ?

![Carte routière](/image/lh.png)

    Il s'agit de la ville du Havre.

## 2. Prendre quelques mesures de base de ce graphe : nombre de sommets et d'arêtes, degré moyen, distribution de degrés, coefficient de clustering. À votre avis, est-ce qu'on retrouve des valeurs similaires pour tout réseau routier ?

 | Mesure                | Résultat |
 | :-------------------- | :------: |
 | $`N`$                 |   761    |
 | $`E`$                 |   1106   |
 | $`\langle k \rangle`$ |  2.907   |
 | $`\langle C \rangle`$ |  0.022   |

![Distribution des degrés](/image/ddegree_lh.png)

    Pour ce qui est de retrouver des valeurs similaires sur tout autre réseau routier, 
    tout dépend de la taille du réseau routier et de son organisation. Sur des villes Européennes, 
    on aura de fortes chances d'avoir un degré moyen et un coefficient de clustering moyen similaire 
    mais si nous prenons des villes des Etats-Unis qui ont un aménagement très structurés en quadrillage, 
    le degré moyen devrait plus être aux alentours de 4.

## 3. (GPS) Toutes les arêtes possèdent un attribut "length" qui correspond à la longueur de l'arête en mètres. Faire une méthode permettant de trouver le plus court chemin entre deux sommets en utilisant l’algorithme de Dijkstra. Visualiser ce chemin en changeant la couleur des arêtes. Tester avec les sommets choisis au hasard.

    Pour ce qui est de la méthode, ma solution consiste à passer deux paramètres 
    à la fonction de route, la source et la destination et de retourner le chemin complet.

```java
    public Path route(Node a, Node b) {
        Dijkstra dijkstra = new Dijkstra(Dijkstra.Element.EDGE, "result", "length");
        dijkstra.init(graph);
        dijkstra.setSource(a);
        dijkstra.compute();
        return dijkstra.getPath(b);
    }
```

    Voici le résultat obtenu en cliquant sur deux noeuds du graphe.

![PPC entre 2 noeuds](image/ppc_dijkstra.png)

## 4. Pour les aventuriers qui se sentent à l'aise avec swing et qui veulent savoir plus sur le modèle événementiel de GraphStream, faire en sorte qu'on puisse choisir les sommets source et destination du plus court chemin en cliquant sur eux. S'inspirer de l'exemple donné ici.

    Pour pouvoir avec le plus court chemin entre 2 noeuds depuis l'interface 
    graphique, il suffit de cliquer sur 2 noeuds à la suite. 
    Recliquer sur un noeud pour annuler l'action.


## 5. En se basant sur la complexité de ces deux algorithmes vus en cours, laquelle de deux approches ci-dessus sera plus efficace pour notre graphe ?

    L'algorithme de Dijkstra est le plus adapté pour connaitre le chemin d'une 
    source vers l'ensemble des autres noeuds dans notre graphe car il est le plus 
    performant lorsqu'un graphe n'a que des arêtes positives.

    De plus, Floyd-Warshall doit calculer l'ensemble des plus courts 
    chemin pour tous les noeuds du graphe avant de pouvoir récupérer le moindre résultat. 

    Pour le calcul du diamétre on a les compléxités suivants :

Floyd-Warshall : $`O(n^3) <=> 761^3 = 440711081`$
    
Dijkstra : $`O(n*(m+log(n))) <=> 761 * (1106 + log(761) = 843858`$

    Théoritiquement, Dijkstra est 522 fois plus rapide.

## 7. Implémenter les deux approches, mesurer leur temps d'exécution. Est-ce que la réalité correspond à vos prévisions théoriques ?

 | Algorithme     | Temps (en seconde) |
 | :------------- | :----------------: |
 | Dijkstra       |        1.8         |
 | Floyd-Warshall |        45.5        |

    Dans notre expérience, on peut constater que l'algorithme de Dijkstra 
    sera en moyenne 25 fois plus rapide que celui de Floyd-Warshall.

    La réalité est donc bien inférieur aux prévisions théoriques.