# FastestPaperBoy ## Question 1 Les données relevées sur ce graphe sont les suivantes : ``` |V|: 761 |E|: 1106 : 2.907 : 0.022 ``` ![Distribution des degrés](images/lh_degrees_distribution.png) *Distribution des degrés* Les caractéristiques de ce graphe doivent être retrouvées dans des réseaux routiers similaires, mais tous les réseaux ne seront pas similaires, comme par exemple les autoroutes. Les autoroutes ont un faible degré moyen puisque ce sont en grande partie des lignes directes. ## Question 6 Pour le choix de l'algotithme entre Dijkstra et Floyd-Warshall, il faut comparer les complexités. Dijkstra est de complexité `O(n log(n) + m)` et Floyd-Warshall de complexité `O(n^3)`. ``` C(n * Dij) = 761 * (761 * log(761) + 761) = 2247791 C(Flo-War) = 761^3 = 440711081 ``` Il est largement préférable de choisir d'appliquer Dijkstra à chaque noeud du graphe. ## Question 7 Mesures de temps d'exécution sur les deux méthodes : ``` Dijkstra : 2.282 secondes Floyd-Warshall : 44.272 secondes ``` La différence entre les deux approches est cohérente, même si le rapport entre les deux coûts ne semble pas aussi grand qu'en théorie (196 en théorie contre 19 en pratique).