[PDF] EXERCICES CHEMINS OPTIMAUX Exercice 1 : Exercice 2

Comment trouver le chemin le plus court entre un point et une droite ?

Pour connaitre le chemin le plus court entre un point A et une droite d, on trace la droite perpendiculaire à d passant par A. On appelle B le point d'intersection entre les deux droites. Alors la distance la plus courte entre le point A et la droite d est la longueur AB.

Comment calculer le nombre de chemins du sommet 4 au sommet 7 ?

Il existe un seul CLPC du sommet 4 au sommet 7. Il existe 20 chemins du sommet 1 au sommet 16. En effet, on doit se diriger 3 fois vers la gauche et 3 fois vers le haut; le nombre c de chemins est donc égal au nombre de façons de choisir les trois positions des arcs horizontaux dans le chemin : c = ? = = = 20 .

Comment calculer la longueur d’un chemin ?

En cas d’égalité, la longueur du CLPC de i à j restera la même s’il existe dans le réseau original un chemin de longueur dij autre que le chemin constitué du seul arc ij ; sinon, dans le nouveau réseau, le seul CLPC de i à j sera le chemin direct i – j réduit au seul arc ij et la distance de i à j sera égale à c’ij . Note 1.

Comment calculer le court chemin entre deux droites parallèles ?

Le court chemin entre deux droites parallèles d et d' est obtenu en traçant n'importe quelle droite perpendiculaire aux deux droites. Si on note A et A' les points d'intersection entre cette perpendiculaire et les droites d et d', alors la distance entre les deux droites est la longueur AA'.