1 files changed, 62 insertions, 0 deletions
diff --git a/THEG/Distances et plus court chemin.md b/THEG/Distances et plus court chemin.md
new file mode 100755
index 0000000..a040318
--- /dev/null
+++ b/THEG/Distances et plus court chemin.md
@@ -0,0 +1,62 @@
+# Rubik's cube
+- noeud = configuration
+- arêtes = 1/4 de tour
+
+# Calcul de distance
+On cherche à trouver la plus petite distance entre le sommet source et tous les sommets destinations
+
+$\rightarrow$ on fait un BFS
+
+![[Pasted image 20250319171722.png]]
+
+**Complexité**: $\Theta(|V| + |E|)$
+
+# Rayon et diamètre
+
+## Excentricité
+
+$exc(x) = max\{ d(x,y) \; | \; y \in V \}$
+
+## Rayon
+
+$rayon(G) = min\{exc(x) \; | \; x \in V\}$
+
+## Diamètre
+
+$diam(G) = max\{exc(x) \; | \; x \in V\}$
+## Centre
+
+$centre(G) = \{x \in V \; | \; exc(x) = rayon(G)\}$
+
+## Périphérie
+
+$périphérie(G) = \{x \in V \; | \; exc(x) = diam(G)\}$
+
+# Dijkstra
+$\rightarrow$ pour les graphes pondérés
+On traite en premier les sommets de distance minimale
+
+![[Pasted image 20250319175639.png]]
+
+**Complexité** :
+- Si todo est un tableau/vecteur : $O(|V|^2 + |E|)$
+- Si todo est un tas min : $O((|V| + |E|)\log |V|)$
+- Si todo est un tas de Fibonacci : $O(|E| + |V|\log |V|)$
+
+# Algorithme de Bellman-Ford
+
+$\rightarrow$ Cas des poids négatifs
+$dist(y,k) =$ distance du PCC allant de $s$ à $y$ avec au plus $k$ arêtes
+$dist(y,k) = \min\{ dist(x,k-1) + w(x,y) \; | \; x \in V \}$
+$$dist(y,0) = \begin{cases}
+0 \quad si \quad s = y \\
+\infty \quad sinon
+\end{cases}$$
+$dist(s,y) = dist(y, |V| - 1)$ ($|V| - 1 =$ nb max d'arête dans un PCC)
+
+![[Pasted image 20250319183624.png]]
+
+### Optimisations
+
+- s'arrêter si rien ne change d'une itération à l'autre $\rightarrow O(|V|.|E|)$
+- lever une exception si le tableau *dist* bouge encore pour l'itération $k = |V|$
+\ No newline at end of file