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

LMD OUARGLA

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

 

 Algorithme de Dijkstra exemple

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




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

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

http://membres.multimania.fr/baekoasis
www.baekoasis.i8.com
soit le graphe
1 2 3 4 5
1 0 15 oo oo 4
2 0 0 oo oo oo
3 oo 3 0 2 oo
4 10 3 oo 0 oo
5 oo oo 7 5 0
Remarque : le graphe est orienté, oo : pas d'arc

Initialisations

S = {1} ; T = {2, 3, 4, 5} ; l = (0, 15, ¥, ¥, 4); p = (NIL, 1, NIL, NIL, 1)

1ère itération

i = 5 car l(5) = min(15, ¥, ¥, 4) = 4
S = {1, 5}; T = {2, 3, 4}
les successeurs de 5 dans T sont 3 et 4
l(3) prend la nouvelle valeur min(¥; l(5) + d(5; 3)) = min(¥; 4 + 7) = 11; p(3) = 5
l(4) prend la nouvelle valeur min(¥; l(5) + d(5; 4)) = 9; p(4) = 5
d'où les nouveaux vecteurs l = (0, 15, 11, 9, 4) et p = (NIL, 1, 5, 5, 1)

2ème itération

i = 4; l(4) = 9
S = {1, 5, 4}; T = {2, 3}
le seul successeur de 4 dans T est 2
l(2) prend la nouvelle valeur min(¥; l(4) + d(4; 2)) = min(15; 9 + 3) = 12; p(2) = 4
d'où les nouveaux vecteurs l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)

3ème itération

i = 3; l(3) = 11
S = {1, 5, 4, 3}; T = {2}
le seul successeur de 3 dans T est 2
l(2) garde sa valeur car min(12; l(3) + d(3; 2)) = min(12; 11 + 3) = 12
d'où les vecteurs inchangés l = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)

4ème itération

i = 2; l(2) = 12
S = {1, 5, 4, 3, 2}; T = {}; FIN
l = (0, 12, 11, 9, 4)
p = (NIL, 4, 5, 5, 1)
Par exemple, le chemin minimal de 1 à 4 est de coût 9.
C'est le chemin 1-5-4, car p(4) = 5 et p(5) = 1.
الرجوع الى أعلى الصفحة اذهب الى الأسفل
 
Algorithme de Dijkstra exemple
الرجوع الى أعلى الصفحة 
صفحة 1 من اصل 1
 مواضيع مماثلة
-
» Algorithme de Dijkstra

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