أداء أقصر خوارزمية مسار في Jung API

Question

أستخدم Jung API لحساب أقصر المسارات بين عدة العقد في الرسوم البيانية الكبيرة المتوسطة (20 إلى 100 عقد). في الوقت الحالي ، أكرر العقد الخاصة بي وأستخدم وظيفة "HistetsPath" البسيطة لحساب أقصر مسار لعقدتين. يتم وضع جميع أقصر المسارات في قائمة ArrayList.

UnweightedShortestPath<Vertex, SEdge> dist = new UnweightedShortestPath<Vertex, SEdge>(undir);
ArrayList<Vertex> tv = new ArrayList<Vertex>(); // contains nodes for shortestpath
ArrayList<Integer> distances = new ArrayList<Integer>(); // for the distances

for (int j = 0; j <tv.size()-1;j++){ //iterate over nodes
Vertex one = tv.get(j);

for (int k = j+1; k<tv.size();k++){ //iterate over next nodes
    Vertex two = tv.get(k);
    Number n = dist.getDistance(one, two);
    int d;
    if (n == null) {
        d = 5000000;
    }
    else {
        d = n.intValue();
    }
    distances.add(d);
}

}

أرغب في تسريع الحساب لأنني يجب أن أحسب هذا للعديد من الرسوم البيانية والعقد. على حد علمي ، يتوفر Dijkstra فقط في Jung API. إذن أسئلتي هي: هل يمكنني استخدام Dijkstra لتعزيز الأداء؟ هل الخوارزميات الأخرى متاحة في Jung API؟ هل من المنطقي استخدام تطبيق رسم بياني آخر يوفر المزيد من الطرق المختلفة لأقصر المسارات؟

شكرا حتى الآن :)

Answer 1

تستخدم فئة UnweightedShortestPath في Jung خوارزمية البحث في الوقت الحالي ، والتي تحتوي على وقت تشغيل O (n^2). تعمل خوارزمية Dijkstra بشكل أساسي ، فقط للرسوم البيانية المرجحة بدلاً من الرسوم البيانية غير المرغوب فيها ، لذلك فهو وقت التشغيل هو أيضًا (n^2).

ومع ذلك ، يبدو أنك مهتم بالمسافات بين جميع أزواج العقد الممكنة في الرسم البياني الخاص بك ، لكنك تستخدم نهجًا زوجيًا. لذا فإن إجمالي وقت التشغيل الخاص بك هو O (n * n^2) = o (n^3). بدلاً من ذلك ، يمكنك استخدام خوارزمية عالمية لأقصر مسار مثل خوارزمية جونسون (http://en.wikipedia.org/wiki/Johnson's_algorithm). هذا هو وقت التشغيل O (n^2 * log (n+ne)). لذلك أسرع قليلا بشكل عام.

لم يتم تنفيذها في Jung على حد علمي ، لكنك قد تكون قادرًا على التخلص منه من البحث عن رمز Google.