# TP Plus courts chemins

## Question 1

Il s'agit de la ville du Havre.

## Question 2

noeuds : 761

arretes : 1106

degres : 2.9067018032073975

clustering : 0.02220762155059133

Distribution :

     1          0.042

     2          0.241

     3          0.494

     4          0.212

     5          0.007

     6          0.001


## Question 6

D'après les complexités des deux algorithmes vu en cours, Dikjstra est plus optimal pour un graphe avec peu de densité

Donc théoriquement il faut utilisé plutot l'algorithme de Dikjstra.

## Question 7

Le temps pour Dijkstra : 511ms.

Le temps pour Floyd-Warshall : 27455ms.

Cela correspond à la prédiction théorique de la question précédente.

## Aller plus loins

J'ai calculé une distance moyenne pour ce graph de 1341,34. Pour ce faire, j'ai utilisé l'algorithme de dikjstra qui
parcour déjà toutes les paires de sommets, et pour chaque paire, j'ajoute la longueurs de l'arrete à la distance total du graphe.

Une fois toutes les longueurs récupérées, je divise la longueur total par le nombre de noeud au carré.