---
# System prepended metadata

title: 'ALGO6 : TD1-9'
tags: ['2021', algo]

---

# ALGO6 : TD1-9
###### tags: `algo` `2021`


![](https://i.imgur.com/HwsVuUR.png)

1.
| Variable | Type               | Ce qu'il représente                                        |
| -------- | ------------------ | ---------------------------------------------------------- |
| X        | Ensemble de sommet | Sommet déjà parcouru (dont la source)                      |
| D        | Tableau d'entier   | Distance minimale entre la source et les sommets du graphe |
| V        | Ensemble de sommet | Sommets du graphe                                          |

2. Par un tableau de sommets : variable V
3. Oui de façon implicite. Extraire et insérer sont représentés par des "-" et des "∪" respectivement.
4. On choisit à chaque fois le sommet le moins loin de tous les sommets qu'on a visités.
5. Non on connaitra juste son le poids minimal mais pas comment le construire.
6. Si n est le nombre de sommets : n-1 fois.
7.
| Opération                 | Taille                |
| ------------------------- | --------------------- |
| let u such as D(u) is min | Taille de V - X       |
| X = X + u                 | 0                     |
| for each ... v in V - X   | Taille de V - X       |
| **Total**                 | (Taille de V - X) * 2 |

8. O(n²) 


---

![](https://i.imgur.com/pJrz41x.png)


| Variable | Ce qu'il représente                        | Type            |
| -------- | ------------------------------------------ | --------------- |
| S        | La presence de l'arete dans S (solution)   | Tableau de bits |
| Cost     | Matrice d'adjacence (arrêtes avec le cout) | Matrice         |
| Dist     | Distance entre sommet et S                 | Liste d'entiers |

2. Le graphe est représenté par une matrice de cout d'adjacence.
3. File à priorité implicite extraire vaut "min{DIST(w)} tel que S(w) = 0" puis on met à jour tout les élément de Dist avec le nouvelle distance pour tous les noeuds en dehors de S. On insere pas dans Dist.
4. Grace à la FAP. On y accède en choisissant min{DIST(w)} tel que S(w) = 0
5. On peut construire le chemin de poids minimal à partir de DIST qui indique les distance les plus courts on retrouve le plus court à partir de la distancem
6.
7. L'iteration principale est répété n-2 fois. 
8.  
| Opération                                  | Taille                   |
| ------------------------------------------ | ------------------------ |
| let u such as D(u) is min                  | Taille de DIST - S       |
| S(u) = 1                                   | 1                        |
| for each ... w in DIST - S                 | Taille de DIST - S       |
| Dist(w) = min(DIST(w),Dist(u) + COST(u,w)) | 1                        |
| **Total**                                  | (Taille de DIST - S) * 2 |

8. La compléxité vaut O(n^2)

---

![](https://i.imgur.com/9xruL8M.png)


| Variable | Ce qu'il représente                 | Type                            |
| -------- | ----------------------------------- | ------------------------------- |
| L        | Cout des aretes                     | Matrice nxn d'entiers           |
| D        | D est la distance avec N \ C        | Tableau d'entiers               |
| C        | Sommet par lesquels on ne passe pas | Les sommet pas dans la solution |

2. Le graphe est représenté par une matrice de cout d'adjacence.
3. File à priorité implicite extraire vaut "élément de C qui minimise D[v]" puis on met à jour tout les élément de Dist avec le nouvelle distance pour tous les noeuds dans C. On insere pas dans Dist.
4. Grace à la FAP. On y accède en choisissant l'élément de C qui minimise D[v]
5. On peut construire le chemin de poids minimal à partir de D qui indique les distance les plus courts on retrouve le plus court à partir de la distance.
6. L'iteration principale est répété n-2 fois. 
7.  
| Opération                                  | Taille                   |
| ------------------------------------------ | ------------------------ |
| v l'élément de C qui minimise D[v]         | Taille de C              |
| C \ {v}                                    | 1                        |
| pour chaque élément w de C                 | Taille de DIST - S       |
| D(w) = min(D(w),Dist() + L(v,w))           | 1                        |
| **Total**                                  | (Taille de DIST - S) * 2 |

8. La compléxité vaut O(n^2)

---

![](https://i.imgur.com/vUh71wc.png)


| Variable | Type               | Ce qu'il représente                      |
| -------- | ------------------ | ---------------------------------------- |
| x0       | Sommet             | Source du graphe                         |
| G        | Graphe             | Graphe                                   |
| d        | Tableau de réel    | Distances entre la source et les sommets |
| pr       | Tableau d'entier   |                                          |
| y, m     | Sommet             | Sommet                                   |
| S        | Ensemble           | Ensemble des sommets de G                |
| M        | Ensemble de sommet | Ensemble des sommets de G sauf x0        |
| CC       | Ensemble de sommet | Ensemble des sommets de G parcouru       |

1. Par un ensemble de sommet créé depuis un type Graphe

2. 


---

![](https://i.imgur.com/xqADOye.png)

| Variable | Type | Ce qu'il représente |
| -------- | ---- | ------------------- |
|          |      |                     |
|          |      |                     |
|          |      |                     |
