README.md

# 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 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).