LMD OUARGLA

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

شاطر | 
 

 Algorithme de Dijkstra

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



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

مُساهمةموضوع: Algorithme de Dijkstra   الأحد أبريل 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
نقاط : 3228
تاريخ التسجيل : 25/11/2008
الموقع : lmdouargla.ahlamontada.com

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

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



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

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

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

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