LMD OUARGLA

LMD OUARGLA
 
الرئيسيةاليوميةس .و .جبحـثالتسجيلدخول

شاطر | 
 

 Algorithme de Dijkstra exemple

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



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

مُساهمةموضوع: Algorithme de Dijkstra exemple   الأحد أبريل 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
 مواضيع مماثلة
-
» Alternatives aux appareils dentaires contraignants et hasardeux
» les types de texte

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