Newer
Older
## 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*
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).