# 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 sont certainement retrouvées dans des réseaux routiers similaires (urbains), ce ne sera pas le cas, en revanche, pour les autoroutes par exemple. Car un graphe d'un trafic autoroutier aurait un faible degré moyen puisque ce sont en grande partie des lignes directes. ## Question 6 Pour le choix de l'algorithme entre Dijkstra et Floyd-Warshall, il faut comparer leur complexité pour notre cas. 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 ``` Appliquer N fois Dijkstra est alors largement préférable. ## 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 observée entre les deux approches est cohérente, même si le rapport des coûts ne semble pas aussi grand qu'en théorie (196 en théorie contre 19 en pratique).