الگوریتم دایکسترا یکی از مشهورترین الگوریتمها در حوزهی نظریه گرافها و مسیریابی است که برای یافتن کوتاهترین مسیر از یک رأس به سایر رأسهای یک گراف وزندار بدون وزنهای منفی به کار میرود. این الگوریتم توسط ادسخر دایکسترا (Edsger Dijkstra) در سال 1956 ارائه شد و از آن زمان تاکنون در حوزههای مختلفی ازجمله شبکههای کامپیوتری، مسیریابی GPS، طراحی مدارهای الکترونیکی و بسیاری از مسائل مرتبط با مسیریابی به کار گرفتهشده است.
لگوریتم دایکسترا برای یافتن کوتاهترین مسیر در یک گراف وزندار جهتدار یا بدون جهت استفاده میشود. فرض کنید گرافی بهصورت G=(V,E)G=(V,E) دادهشده که:
۱. مقدار فاصلهی هر رأس از مبدأ را ∞ در نظر میگیریم، بهجز رأس مبدأ که مقدار آن ۰ است.
۲. یک مجموعهی بازدید نشده (Unvisited Nodes) ایجاد میکنیم که شامل تمامی رأسها است.
3. در هر گام، رأسی را که کمترین مقدار فاصله را دارد، انتخاب کرده و آن را قطعی (Visited) میکنیم.
4. تمامی همسایگان این رأس را بررسی کرده و مقدار فاصلهی آنها را بهروزرسانی میکنیم.
5. این روند را تکرار میکنیم تا زمانی که تمامی گرهها بررسی شوند یا به هدف موردنظر برسیم.
الگوریتم دایکسترا در بسیاری از زمینهها استفاده میشود، ازجمله:
مسیریابی در شبکههای کامپیوتری: برای یافتن کوتاهترین مسیر بین دو دستگاه در یک شبکه.
سیستمهای ناوبری GPS: برای یافتن کوتاهترین مسیر بین دو مکان جغرافیایی.
بازیهای کامپیوتری: برای حرکت هوشمند شخصیتها در محیطهای مجازی.
زمانبندی پروازها: برای یافتن کوتاهترین مسیر بین دو فرودگاه.
پیادهسازی الگوریتم دایکسترا در سی شارپ
در زیر یک پیادهسازی ساده از الگوریتم دایکسترا به زبان سی شارپ ارائهشده است
الگوریتم دایکسترا یکی از مشهورترین الگوریتمها در حوزهی نظریه گرافها و مسیریابی است که برای یافتن کوتاهترین مسیر از یک رأس به سایر رأسهای یک گراف وزندار بدون وزنهای منفی به کار میرود. این الگوریتم توسط ادسخر دایکسترا (Edsger Dijkstra) در سال 1956 ارائه شد و از آن زمان تاکنون در حوزههای مختلفی ازجمله شبکههای کامپیوتری، مسیریابی GPS، طراحی مدارهای الکترونیکی و بسیاری از مسائل مرتبط با مسیریابی به کار گرفتهشده است.۱. نحوهی عملکرد الگوریتم دایکسترا۱.۱. تعریف مسئلهالگوریتم دایکسترا برای یافتن کوتاهترین مسیر در یک گراف وزندار جهتدار یا بدون جهت استفاده میشود. فرض کنید گرافی بهصورت G=(V,E)G=(V,E) دادهشده که: VV مجموعهای از رأسها (گرهها) است. EE مجموعهای از یالها است که دو رأس را به هم متصل میکنند. هر یال وزنی (cost) دارد که بیانگر هزینهی حرکت از یک رأس به رأس دیگر است.۱.۲. مراحل الگوریتم۱. مقدار فاصلهی هر رأس از مبدأ را ∞ در نظر میگیریم، بهجز رأس مبدأ که مقدار آن ۰ است.۲. یک مجموعهی بازدید نشده (Unvisited Nodes) ایجاد میکنیم که شامل تمامی رأسها است.3. در هر گام، رأسی را که کمترین مقدار فاصله را دارد، انتخاب کرده و آن را قطعی (Visited) میکنیم.4. تمامی همسایگان این رأس را بررسی کرده و مقدار فاصلهی آنها را بهروزرسانی میکنیم.5. این روند را تکرار میکنیم تا زمانی که تمامی گرهها بررسی شوند یا به هدف موردنظر برسیم.کاربردهای الگوریتم دایکستراالگوریتم دایکسترا در بسیاری از زمینهها استفاده میشود، ازجمله: مسیریابی در شبکههای کامپیوتری: برای یافتن کوتاهترین مسیر بین دو دستگاه در یک شبکه. سیستمهای ناوبری GPS: برای یافتن کوتاهترین مسیر بین دو مکان جغرافیایی. بازیهای کامپیوتری: برای حرکت هوشمند شخصیتها در محیطهای مجازی. زمانبندی پروازها: برای یافتن کوتاهترین مسیر بین دو فرودگاه.پیادهسازی الگوریتم دایکسترا در سی شارپدر زیر یک پیادهسازی ساده از الگوریتم دایکسترا به زبان سی شارپ ارائهشده است.
using System;
using System.Collections.Generic;
class Dijkstra
{
private static int V = 6; // تعداد گرهها
private int MinDistance(int[] dist, bool[] sptSet)
{
int min = int.MaxValue, minIndex = -1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
minIndex = v;
}
return minIndex;
}
private void PrintSolution(int[] dist)
{
Console.WriteLine("گره \t فاصله از گره شروع");
for (int i = 0; i < V; i++)
Console.WriteLine(i + " \t\t " + dist[i]);
}
public void DijkstraAlgorithm(int[,] graph, int src)
{
int[] dist = new int[V]; // آرایه برای ذخیره کوتاهترین فاصله از گره شروع
bool[] sptSet = new bool[V]; // آرایه برای مشخص کردن گرههایی که فاصلهشان نهایی شده است
for (int i = 0; i < V; i++)
{
dist[i] = int.MaxValue;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = MinDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v])
dist[v] = dist[u] + graph[u, v];
}
PrintSolution(dist);
}
public static void Main()
{
int[,] graph = new int[,] {
{ 0, 4, 0, 0, 0, 0 },
{ 4, 0, 8, 0, 0, 0 },
{ 0, 8, 0, 7, 0, 4 },
{ 0, 0, 7, 0, 9, 14 },
{ 0, 0, 0, 9, 0, 10 },
{ 0, 0, 4, 14, 10, 0 }
};
Dijkstra dijkstra = new Dijkstra();
dijkstra.DijkstraAlgorithm(graph, 0);
}
}
توضیح کد
مثال حلشده
فرض کنید گراف زیر را داریم:
(0)
/ | \
4/ | \0
/ | \
(1)--(2)--(3)
| / \ |
| 8/ \7 |
| / \ |
(4)-------(5)
9
در این گراف، گره شروع (0) است. الگوریتم دایکسترا فاصلههای کوتاهترین مسیر از گره (0) به سایر گرهها را محاسبه میکند.
خروجی برنامه بهصورت زیر خواهد بود
گره فاصله از گره شروع
0 0
1 4
2 12
3 19
4 21
5 16
این خروجی نشان میدهد که کوتاهترین مسیر از گره (0) به گره (5) با فاصله 16 است.
الگوریتم دایکسترا یک ابزار قدرتمند برای یافتن کوتاهترین مسیر در گرافهای وزندار است. باوجود سادگی، این الگوریتم در بسیاری از کاربردهای عملی استفاده میشود و درک آن برای هر دانشجوی علوم کامپیوتر یا مهندسی نرمافزار ضروری است. پیادهسازی این الگوریتم در زبانهای برنامهنویسی مانند سی شارپ نیز به درک بهتر مفاهیم آن کمک میکند.
