(321 امتیاز از 89 رای)
Loading...
الگوریتم دایجسترا با زبان C سی همراه سورس کد
در این پست برای شما کاربران عزیز، الگوریتم دایجسترا با زبان C سی همراه سورس کد را آماده کرده ایم که امیدواریم مورد استفاده قرار گیرد.
در نظریه گراف، الگوریتم دایجسترا (Dijkstra’s algorithm) یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دایْکْسْترا در سال ۱۹۵۹ ارایه شد.
این الگوریتم یک الگوریتم پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌دار حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد استفاده کرد که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.
الگوریتم دایکسترا به نام کوتاه ترین مسیر تک منبع نیز معروف است و شبیه الگوریتم پریم است. در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی‌کند و خروجی مناسبی را نمی دهد و باید از الگوریتم‌های دیگر مثل الگوریتم بلمن فورد که پیچیدگی زمانی آنها بیشتر است استفاده کنیم.
در ادامه می توانید قسمت های از کد الگوریتم دایجسترا با زبان C سی را ملاحظه کنید.
تکه کد برنامه الگوریتم دایجسترا با زبان C سی:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | <strong><span style="color: #ff0000;">جهت دریافت کد کامل این برنامه از قسمت خرید محصول اقدام کنید</span></strong> #include<stdio.h> #include<conio.h> #include<process.h> #include<string.h> #include<math.h> #define IN 99 #define N 6 int dijkstra(int cost[][N], int source, int target); int dijsktra(int cost[][N],int source,int target) { int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j; char path[N]; for(i=1;i< N;i++) { dist[i] = IN; prev[i] = -1; } start = source; selected[start]=1; dist[start] = 0; while(selected[target] ==0) { min = IN; m = 0; for(i=1;i< N;i++) { d = dist[start] +cost[start][i]; if(d< dist[i]&&selected[i]==0) { dist[i] = d; prev[i] = start; } if(min>dist[i] && selected[i]==0) { min = dist[i]; m = i; } } start = m; selected[start] = 1; } start = target; j = 0; while(start != -1) { path[j++] = start+65; start = prev[start]; } path[j]=' '; strrev(path); printf("%s", path); return dist[target]; } |
هیچ نظری ثبت نشده است