blob: a04031890ca0fbd9ebef78243847c2bfad25caff (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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|$
|
