Chemin dans un réseau (1)
On considère le réseau local d'un Lycée relié au réseau local d'une Maison et à une Webcam au travers de quatre routeurs nommés Routeur1, Routeur2, Routeur3 et Routeur4. Les routeurs, les réseaux locaux et la webcam constituent les nœuds d'un réseau public.
On peut modéliser cette interconnexion par un graphe comme ci-dessous :
Exemple de réseau
flowchart LR
A([Lycee]) <--> B([Routeur1])
B <--> E([Routeur2])
C([Webcam]) <--> B
D([Routeur3]) <--> G([Maison])
D <--> E
E <--> F([Routeur4])
F <--> DChaque nœud dispose d'une table de routage qui lui associe, pour chaque nœud d'arrivée, la prochaine étape du chemin. Si une destination n'est pas référencée dans la table de routage, on utilise une route par défaut, indiquée ici par "Autres".
Ainsi la table de routage du Routeur2 est la suivante :
| Destination | Prochaine étape |
|---|---|
| Lycee | Routeur1 |
| Webcam | Routeur1 |
| Autres | Routeur4 |
Quand un paquet arrive sur un routeur, on vérifie si l'adresse est présente dans la table de routage et on trouve la prochaine étape. Si l'adresse n'est pas présente, on prend la route par défaut.
Ainsi, si un paquet arrive au Routeur2 avec pour adresse de destination Maison, il est redirigé vers le Routeur4.
Une table de routage est représentée en Python par un dictionnaire dont :
-
les clés sont les chaînes de caractères correspondant aux noms des nœuds de destination, ou
"Autres"pour la route par défaut, -
les valeurs associées sont des chaînes de caractères représentant les nœuds vers lesquels sont redirigés les paquets.
Table de routage du Routeur2
table_routeur2 = {
"Lycee": "Routeur1",
"Webcam": "Routeur1",
"Autres": "Routeur4"
}
On représente l'ensembles des tables de routage dans un dictionnaire associant à chaque nœud du réseau sa table de routage. On souhaite pouvoir déterminer à l'aide de celles-ci le chemin emprunté par un paquet émis d'un nœud du réseau vers un autre.
Exemple
Un paquet issu du réseau du Webcam et adressé à celui de la Maison devra emprunter le chemin Webcam → Routeur1 → Routeur2 → Routeur4 → Routeur3 → Maison.
Dans le cas où les réseaux d'arrivée et de départ sont identiques, les paquets ne sortent pas du réseau.
Écrire une fonction récursive trouver_chemin qui :
-
prend en paramètres un dictionnaire
reseaureprésentant un tel réseau, deux chaînes de caractèresdepartetarriveequi représentent les nœuds de départ et d'arrivée ; -
renvoie la liste des nœuds représentant le chemin parcouru, en incluant les nœud de départ et d'arrivée.
On garantit qu'il existe un tel chemin entre chaque paire de nœuds du réseau.
Exemples
>>> trouver_chemin(mon_reseau, "Webcam", "Maison")
['Webcam', 'Routeur1', 'Routeur2', 'Routeur4','Routeur3', 'Maison']
>>> trouver_chemin(mon_reseau, "Lycee", "Lycee")
['Lycee']
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)