Tham khảo tài liệu 'le probleme du plus court chemin - đường đi ngắn nhất', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chapitre 3. Le Probleme du Plus Court Chemin CHAPITRE 3. LE PROBLEME DU PLUS COURT CHEMIN. Les problèmes de cheminement dans les graphes en particulier la recherche d un plus court chemin comptent parmi les problèmes les plus anciens de la théorie des graphes et les plus importants par leurs applications. . DEFINITION. Soit G X U un graphe valué on associe à chaque arc u i j une longueur l u ou lij . Le Problème du plus court chemin entre i et j est de trouver un chemin p i j de i à j tel que l M z l u u soit minimal. Interpretation de l ụ coũt de transport dépense de construction temps nécessaire de parcours . Remarque. La recherche du plus court chemin est analogue à la recherche du plus long chemin. Les algorithmes seront différents suivant les propriétés des graphes l u 0 V u e U. Les longueurs l u égales l u 1 V u e U. problème du plus court chemin en nombre d arcs G sans circuit. G et l u quelconques. Truong My Dung Mail tmdung@ 28 Chapitre 3. Le Probleme du Plus Court Chemin Et suivant le problème considéré Recherche du plus court chemin d un sommet à tous les autres Recherche du plus court chemin entre tous les couples de sommets. . PRINCIPE D OPTIMALITE. Le principe d optimalité énonce le fait que les sous-chemins des plus courts chemins sont des plus courts chemins la programmation dynamique repose sur ce principe fondamental . LEMME. Soient un graphe G X U et une fonction de pondération l X x X R Soit C X1 X2 . Xk un plus court chemin de Xi à Xk et pour tout i j tel que 1 i j k soit Cij Xi Xi 1 . Xj un sous chemin de C allant de Xi à Xj. Alors Cij est un plus court chemin de Xi à Xj. Principe des algorithmes de recherche de chemins minimaux Une distance d i est associée à xi. En fin d algorithme cette distance représente la longueur d un plus court chemin de l origine au sommet considéré. . VARIANTES DU PROBLEME D UN SOMMET A TOUS LES AUTRES. Ce problème est aussi appelé le problème de recherche du plus court chemin à origine .
