# 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|$