دانلود سورس الگوریتم دایکسترا در سی پلاس پلاس

در این قسمت تیم کدگیت فایل دانلود سورس الگوریتم دایکسترا در سی پلاس پلاس را آماده کرده است. برای اجرای پروژه، کافیست فایل دانلود شده را به پروژه خود اضافه و آن را اجرا کنید. پیشنهاد میشود قبل از دانلود، آموزشهای ابتدایی سی پلاس پلاس را بخوانید.

الگوریتم دایکسترا

در نظریه گراف، الگوریتم دیکسترا (به انگلیسی: Dijkstra’s algorithm) یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندیعلوم رایانه، اِدْسْخِر دیْکْسْترا در سال ۱۹۵۹ ارایه شد.

این الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.

یک نمونه خروجی برنامه به صورت زیر می‌باشد:

Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11

بخشی از سورس کد الگوریتم دایکسترا در سی پلاس پلاس به صورت زیر می‌باشد:

void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed
sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet, there is an edge from 
// u to v, and total weight of path from src to v through u is 
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
&& dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array
printSolution(dist, V);
}