تقدم هذه المقالة خوارزمية Dijkstra المبنية على Java في شكل أمثلة وأعتقد أنها ستكون مفيدة للقراء في دراسة وتعلم خوارزميات مجال بنية البيانات.
اقترح ديكسترا خوارزمية لإنشاء أقصر مسار لكل قمة بترتيب متزايد لطول المسار بين كل قمة ونقطة المصدر v. أي، ابحث أولاً عن أقصر مسار بأقصر طول، ثم استخدمه للعثور على أقصر مسار بأقصر طول تالي، وهكذا، حتى يتم العثور على جميع المسارات الأقصر من نقطة المصدر v إلى القمم الأخرى.
تنفيذ الكود هو كما يلي:
package com.algorithm.impl; public class Dijkstra { public static int M = 10000; 3,2000,7,M}, {3,0,4,2,M}, {M,4,0,5,4}, {7,2,5,0,6}, {M,M,4,6,0} }; int[][]weight2 = { {0,10,M,30,100}, {M,0,50,M,M}, {M,M,0, M,10}, {M,M,20,0,60}, {M,M,M,M,0} }; dijkstra(weight2,start); for(int i = 0;i < shortPath. length;i++) System.out.println("أقصر مسافة من "+start+" إلى "+i+" هي: "+shortPath[i ] } public static int[] dijkstra(int[][] الوزن, int start) { // يقبل مصفوفة وزن للرسم البياني الموجه، وبداية رقم نقطة البداية (مرقمة من 0، ويتم تخزين الرأس في المصفوفة) // يُرجع مصفوفة int[]، مما يشير إلى طول أقصر مسار من البداية إليه int n =weight.length ; // عدد القمم int[] shortPath = new int[n]; // احفظ المسار الأقصر من البداية إلى النقاط الأخرى String[] path = new String[n]; المسار من البداية إلى النقاط الأخرى تمثيل السلسلة لـ (int i=0;i<n;i++) path[i]=new String(start+"-->"+i); int[] Visit = new int[n]; // تحديد ما إذا كان أقصر مسار إلى القمة الحالية تم البحث، 1 يعني أنه تم العثور عليه // التهيئة، تم العثور على القمة الأولى shortPath[start] = 0; Visit[start] = 1; for(int count = 1; count < n; count++) { // لإضافة رؤوس n-1 int k = -1; // حدد قمة غير محددة أقرب إلى قمة البداية الأولية int dmin = Integer.MAX_VALUE; for(int i = 0; i < n; i++) { if(visited [i] == 0 &&weight[start][i] < dmin) { dmin =weight[start][i] k = } } // حدد القمة المحددة حديثًا على أنها أقصر مسار تم العثور عليه، وأقصر مسار للبدء هو dmin shortPath[k] = dmin Visit[k] = 1; // مع k كنقطة وسطية، قم بتصحيح المسار from البدء في مسافة النقاط غير المرغوب فيها for(int i = 0; i < n; i++) { if(visited[i] == 0 &&weight[start][k] +weight[k][i] <weight[start] [أنا]) { الوزن[بدء] [i] = الوزن [بدء] [ك] + الوزن [ك] [i] = المسار [ك] + "-->" + i؛ 0; i < n; i++) { System.out.println("أقصر مسار من "+start+" إلى "+i+" هو: "+path[i] }); System.out.println("=====================================================================System.out. }}نتيجة تشغيل هذا البرنامج هي:
أقصر مسار من 0 إلى 0 هو: 0-->0 أقصر مسار من 0 إلى 1 هو: 0-->1 أقصر مسار من 0 إلى 2 هو: 0-->3-->2 من أقصر مسار من 0 إلى 3 هو: 0-->3 أقصر مسار من 0 إلى 4 هو: 0-->3-->2-->4==== ============================= أقصر مسافة من 0 إلى 0 هي : 0 من 0 إلى 1 أقصر مسافة من 0 إلى 2 هي: 50 أقصر مسافة من 0 إلى 3 هي: 30 أقصر مسافة من 0 إلى 4 هي: 60