tailieunhanh - Phần tích thiết kế giải thuật (phần 8)

Tham khảo tài liệu 'phần tích thiết kế giải thuật (phần 8)', 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 Problème 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 S l u u soit minimal. Interprétation de l p 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 Problème 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 .