Chemin dans un réseau (2)
On considère le réseau local du 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 du réseau.
On peut modéliser cette interconnexion par un graphe orienté. Les flèches indiquent vers quel nœud sont redirigés les paquets, en fonction des tables de routage configurées dans chaque routeur. (On ne considère que les chemins par défaut.)
On souhaite pouvoir déterminer le chemin emprunté d'un nœud du réseau vers un autre.
Voici un exemple de réseau
On représente le réseau avec ses connexions physiques :
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 |
Ainsi on représente ci-dessous le même réseau, mais en ne prenant en compte que les routes par défaut.
flowchart LR
A([Lycee]) --> B([Routeur1])
B --> A
B --> E([Routeur2])
C([Webcam]) --> B
B --> C
D([Routeur3]) --> G([Maison])
E --> B
D --> E
E --> F([Routeur4])
F --> D
G --> DUn paquet issu du réseau du Lycee et adressé à celui de la Maison devra emprunter le chemin Lycee - 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.
Par contre, imaginons qu'une panne survient dans la liaison entre le Routeur3 et le Routeur2 :
flowchart LR
A([Lycee]) --> B([Routeur1])
B --> A
B --> E([Routeur2])
C([Webcam]) --> B
B --> C
D([Routeur3]) --> G([Maison])
E --> B
E --> F([Routeur4])
F --> D
G --> DDans ce cas, il n'y a pas de chemin pour aller du réseau du Maison vers celui du Lycee. Il sera nécessaire de modifier les tables de routage.
On représente ce réseau par un dictionnaire dans lequel :
-
les clés sont les chaînes de caractères correspondant aux noms des nœuds,
-
les valeurs associées sont des listes de chaînes de caractères représentant les nœuds vers lesquels peuvent être redirigés les paquets.
Écrire une fonction récursive trouver_chemin qui :
-
prend en paramètres un dictionnaire
reseaureprésentant un tel réseau, une chaîne de caractèresdepartqui représente le nœud de départ et une chaîne de caractèresarriveequi représente le nœud d'arrivée ; -
renvoie la liste des nœuds représentant le chemin parcouru, en incluant les nœuds de départ et d'arrivée.
La fonction prend également en paramètre le dictionnaire visites, ayant la valeur None pour valeur par défaut. Cette variable contiendra les nœuds déjà visités, associés à la valeur True.
On garantit que, si un chemin existe, celui-ci est unique.
Exemples
>>> mon_reseau = {
... "Lycee": ["Routeur1"],
... "Routeur1": ["Lycee", "Routeur2", "Webcam"],
... "Webcam": ["Routeur1"],
... "Routeur3": ["Maison", "Routeur2"],
... "Routeur2": ["Routeur1", "Routeur4"],
... "Routeur4": ["Routeur3"],
... "Maison": ["Routeur3"],
... }
>>> trouver_chemin(mon_reseau, "Lycee", "Maison")
['Lycee', 'Routeur1', 'Routeur2', 'Routeur4', 'Routeur3', 'Maison']
>>> trouver_chemin(mon_reseau, "Lycee", "Lycee")
['Lycee']
>>> mon_reseau_avec_panne = {
... "Lycee": ["Routeur1"],
... "Routeur1": ["Lycee", "Routeur2", "Webcam"],
... "Webcam": ["Routeur1"],
... "Routeur3": ["Maison"],
... "Routeur2": ["Routeur1", "Routeur4"],
... "Routeur4": ["Routeur3"],
... "Maison": ["Routeur3"],
... }
>>> trouver_chemin(mon_reseau_avec_panne, "Maison", "Lycee")
[]
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)