# FastestPaperBoy

## Question 1

Les données relevées sur ce graphe sont les suivantes :
```
|V|: 761
|E|: 1106
<d>: 2.907
<C>: 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.