|
خوارزمية ديكستراخوارزمية ديكسترا 
خوارزمية ديكسترا (بالإنجليزية: Dijkstra's algorithm) هي خوارزمية تعنى بحل مسألة إيجاد المسار الأقصر بين عقدتين في بيان لا يحتوي على وصلات ذات أوزان سلبية.[2][3][4] الخوارزمية مفيدة في عدة تطبيقات، مثل إيجاد الطريق الأقصر بين مدينتين ضمن خريطة، حيث قد تمثل أوزان الوصلات طول الشارع أو مستوى الازدحام في ذلك الشارع أو مجموعهما أو أي معيار مناسب آخر. واضع هذه الخوارزمية هو الهولندي ادسخر دكسترا سنة 1959. تعريف المسألةلدينا بيان حيث انه بيان موزون ومترابط، أوزان وصلاته غير سالبة: ، ولتكن عقدتين ضمن هذا البيان. نريد أن نجد مساراً بسيطاً يربط بين s و-t على أن يكون وزن هذا المسار (المُعرّف على أساس مجموع أوزان الوصلات التي يتألف منها) أصغر ما يمكن. هذه هي المسألة بشكل عام ولكن الخوارزمية تحل مسألة أكثر عموميةً من هذه تتمثل في إيجاد أقصر مسار بين العقدة v وجميع العقد الأخرى. الخوارزمية شرح الخوارزميةسنطلق على العقدة التي نبدأ منها اسم العقدة الأولية. لتكن المسافة حتى العقدة Y هي المسافة من العقدة الأولية حتى العقدة Y. ستقوم خوارزمية دايكسترا بإسناد قيم معينة للمسافات وتحاول بعد ذلك القيام بتحسين هذه المسافات خطوة بعد خطوة.
الخوارزمية تعتمد بشكل كبير على انه إذا وجدنا المسار الأقصر بين v و-u لنُسمه بحيث أن k هو طول المسار ووزنه هو و- , حينئذ إذا نظرنا للمسارات الجزئية من v حتى نجد حينها أنها هي الأقصر. وهذه المُعاينة تعتمد على أنَّ الأوزان موجبة . كود الخوارزميةما يلي هو تطبيق الخوارزمية بلغة java,[5] وهذا التطبيق هو ليس الأفضل بالضرورة ولكنه نموذج لطريقة التطبيق : class Dijkstra
{
double[] dist = new double[G.V()];
Edge[] pred = new Edge[G.V()];
public Dijkstra(WeightedDigraph G, int s)
{
boolean[] marked = new boolean[G.V()];
for (int v = 0; v <G.V(); v++)
dist[v] = Double.POSITIVE_INFINITY;
MinPQplus<Double, Integer> pq;
pq = new MinPQplus<Double, Integer>(); \\Priority Queue
dist[s] = 0.0;
pq.put(dist[s], s);
while (!pq.isEmpty())
{
int v = pq.delMin();
if (marked[v]) continue;
marked(v) = true;
for (Edge e : G.adj(v))
{
int w = e.to();
if (dist[w]> dist[v] + e.weight())
{
dist[w] = dist[v] + e.weight();
pred[w] = e;
pq.insert(dist[w], w);
}
}
}
}
}
الاستخداماتتستخدم هذه الخوارزمية بشكل رئيسي في تطبيقات حساب الطرق مثل خرائط جوجل. فبفضل هذه الخوارزمية يتم إيجاد أقصر طريق بين موقعين. حيث يتم تمثيل شبكة الطرق على شكل رسم بياني والمواقع على شكل عُقد أو نقاط في هذه الشبكة، ومن ثم يتم حساب أقرب مسافة في هذه الشبكة بين أي نقطتين فيها. كذلك تستخدم هذه الخوارزمية في مجال شبكات الإنترنت كخوارزمية توجيه في بعض البروتوكولات مثل: بروتوكول الربط بين الأنظمة الوسيطية. روابط خارجيةمراجع في كومنز صور وملفات عن Dijkstra's algorithm.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
