LMD OUARGLA
هل تريد التفاعل مع هذه المساهمة؟ كل ما عليك هو إنشاء حساب جديد ببضع خطوات أو تسجيل الدخول للمتابعة.

LMD OUARGLA

LMD OUARGLA
 
الرئيسيةأحدث الصورالتسجيلدخول

 

 Algorithme de Dijkstra

اذهب الى الأسفل 
3 مشترك
كاتب الموضوعرسالة
Prooof




عدد المساهمات : 12
نقاط : 5492
تاريخ التسجيل : 21/04/2009

Algorithme de Dijkstra Empty
مُساهمةموضوع: Algorithme de Dijkstra   Algorithme de Dijkstra Icon_minitimeالأحد أبريل 26, 2009 2:59 pm

http://membres.multimania.fr/baekoasis
www.baekoasis.i8.com


Algorithme de Dijkstra est un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres.
Numérotons les sommets du graphe G = (V, E) de 1 à n. Supposons que l'on s'intéresse aux chemins partant du sommet 1. On construit un vecteur l = (l(1); l(2); ...; l(n)) ayant n composantes tel que l(j) soit égal à la longueur du plus court chemin allant de 1 au sommet j.
On initialise ce vecteur à c1,j, c'est-à-dire à la première ligne de la matrice des coûts du graphe, définie comme indiqué ci-dessous :

0 si i= j
Cij = ∞ si i≠ j et (i , j) E
d(i , j) si i≠ j et (i , j) E

où d(i,j) est le poids (la longueur) de l'arc (i, j). Les cij doivent être strictement positifs.

On construit un autre vecteur p pour mémoriser le chemin pour aller du sommet 1 au sommet voulu. La valeur p(i) donne le sommet qui précède i dans le chemin.

On considère ensuite deux ensembles de sommets, S initialisé à {1} et T initialisé à {2, 3, ..., n}. ہ chaque pas de l'algorithme, on ajoute à S un sommet jusqu'à ce que S = V de telle sorte que le vecteur l donne à chaque étape le coût minimal des chemins de 1 aux sommets de S.

Description de l'algorithme de Dijkstra
On suppose ici que le sommet de départ (qui sera la racine de l'arborescence) est le sommet 1. Notons qu'on peut toujours renuméroter les sommets pour que ce soit le cas.

Initialisations
l(j) = c1,j et p(j) = NIL, pour 1 <= j <= n
Pour 2 <= j <= n faire
Si c1,j < ∞ alors p(j) = 1.
S = {1} ; T = {2, 3, ..., n}.

Itérations
Tant que T n'est pas vide faire
Choisir i dans T tel que l(i) est minimum
Retirer i de T et l'ajouter à S
Pour chaque successeur j de i, avec j dans T, faire
Si l(j) > l(i) + d(i, j) alors
l(j) = l(i) + d(i, j)
p(j) = i
Ecrire un programme qui implémente l’algorithme de Dijkstra.
الرجوع الى أعلى الصفحة اذهب الى الأسفل
abdelwahab




عدد المساهمات : 8
نقاط : 5610
تاريخ التسجيل : 25/11/2008
الموقع : lmdouargla.ahlamontada.com

Algorithme de Dijkstra Empty
مُساهمةموضوع: رد: Algorithme de Dijkstra   Algorithme de Dijkstra Icon_minitimeالإثنين أبريل 27, 2009 1:26 am

شـــــــــــكرا على الموضوع و نعدك بالحل العاجل
الرجوع الى أعلى الصفحة اذهب الى الأسفل
http://sellami.abdelwahab.googlepages.com
Pidro_hmd




عدد المساهمات : 1
نقاط : 5448
تاريخ التسجيل : 30/04/2009

Algorithme de Dijkstra Empty
مُساهمةموضوع: رد: Algorithme de Dijkstra   Algorithme de Dijkstra Icon_minitimeالجمعة مايو 15, 2009 1:25 pm

نشكرك على المساعدة ....................... تحياتي
الرجوع الى أعلى الصفحة اذهب الى الأسفل
 
Algorithme de Dijkstra
الرجوع الى أعلى الصفحة 
صفحة 1 من اصل 1
 مواضيع مماثلة
-
» Algorithme de Dijkstra exemple

صلاحيات هذا المنتدى:لاتستطيع الرد على المواضيع في هذا المنتدى
LMD OUARGLA :: رياضيات و إعلام آلي :: قســــم البرمجة-
انتقل الى: