کوتاهترین مسیر یاب در سی‌شارپ
برای حل مسائل مربوط به پیدا کردن کوتاهترین مسیر در گراف‌ها، الگوریتم‌های مختلفی وجود دارند. یکی از معروف‌ترین این الگوریتم‌ها، الگوریتم دیکسترا (Dijkstra's Algorithm) است. این الگوریتم به ما امکان می‌دهد تا کوتاهترین مسیر را از یک گره مبدا به سایر گره‌ها در یک گراف غیر منفی پیدا کنیم.
الگوریتم دیکسترا
الگوریتم دیکسترا از یک گراف وزن‌دار شروع می‌کند. در اینجا، وزن هر یال نشان‌دهنده هزینه یا فاصله بین دو گره است. این الگوریتم به ترتیب زیر عمل می‌کند:
- ایجاد یک مجموعه: ابتدا یک مجموعه خالی برای گره‌های دیده نشده ایجاد می‌شود.
- تنظیم فاصله‌ها: فاصله از گره مبدا به خودش صفر است و به سایر گره‌ها بی‌نهایت (Infinity) تنظیم می‌شود.
- انتخاب گره بهینه: گره‌ای که کمترین فاصله را دارد، انتخاب می‌شود و به مجموعه گره‌های دیده‌شده اضافه می‌گردد.
- به‌روزرسانی فاصله‌ها: فاصله‌های گره‌های مجاور به‌روزرسانی می‌شوند. اگر مسیر جدید کوتاه‌تر از مسیر قبلی باشد، فاصله جدید ثبت می‌شود.
- تکرار: این مراحل تا زمانی که همه گره‌ها دیده شوند، تکرار می‌شود.
کد نمونه در سی‌شارپ
در زیر یک کد نمونه برای پیاده‌سازی الگوریتم دیکسترا در سی‌شارپ آورده شده است:
```csharp
using System;
using System.Collections.Generic;
class Graph
{
private int vertices;
private List<Tuple<int, int>>[] adjacencyList;
public Graph(int v)
{
vertices = v;
adjacencyList = new List<Tuple<int, int>>[v];
for (int i = 0; i < v; i++)
{
adjacencyList[i] = new List<Tuple<int, int>>();
}
}
public void AddEdge(int source, int destination, int weight)
{
adjacencyList[source].Add(Tuple.Create(destination, weight));
adjacencyList[destination].Add(Tuple.Create(source, weight)); // برای گراف غیر جهت‌دار
}
public void Dijkstra(int startVertex)
{
int[] distances = new int[vertices];
bool[] shortestPathTree = new bool[vertices];
for (int i = 0; i < vertices; i++)
{
distances[i] = int.MaxValue;
shortestPathTree[i] = false;
}
distances[startVertex] = 0;
for (int count = 0; count < vertices - 1; count++)
{
int u = MinDistance(distances, shortestPathTree);
shortestPathTree[u] = true;
foreach (var edge in adjacencyList[u])
{
int v = edge.Item1;
int weight = edge.Item2;
if (!shortestPathTree[v] && distances[u] != int.MaxValue && distances[u] + weight < distances[v])
{
distances[v] = distances[u] + weight;
}
}
}
PrintSolution(distances);
}
private int MinDistance(int[] distances, bool[] shortestPathTree)
{
int min = int.MaxValue, minIndex = -1;
for (int v = 0; v < vertices; v++)
{
if (!shortestPathTree[v] && distances[v] <= min)
{
min = distances[v];
minIndex = v;
}
}
return minIndex;
}
private void PrintSolution(int[] distances)
{
Console.WriteLine("Vertex Distance from Source");
for (int i = 0; i < vertices; i++)
{
Console.WriteLine($"{i}\t\t{distances[i]}");
}
}
}
```
در این کد، یک کلاس Graph ایجاد شده است که شامل متدهای مختلفی برای افزودن یال و اجرای الگوریتم دیکسترا می‌باشد.
نتیجه‌گیری
در نهایت، الگوریتم دیکسترا برای حل مسائل مربوط به کوتاهترین مسیر بسیار کارآمد و محبوب است. با استفاده از این الگوریتم، می‌توانیم به راحتی و با صرف زمان کم، کوتاهترین مسیرها را در گراف‌های پیچیده بیابیم.
