كيفية تحسين خوارزمية Dijkstra للحصول على مسار أقصر واحد بين العقدتين؟

Question

كنت أحاول أن أفهم هذا التنفيذ في C من خوارزمية Dijkstra وفي الوقت نفسه ، قم بتعديلها بحيث يتم العثور على أقصر مسار بين العقدتين المحددين (المصدر والوجهة).

ومع ذلك ، لا أعرف بالضبط ماذا تفعل. الطريقة التي أراها ، لا يوجد شيء لأفعله ، لا يمكنني أن أتغير d[] أو prev[] تسبب تلك المصفوفات تجميع بعض البيانات المهمة لأقصر حساب المسار.

الشيء الوحيد الذي يمكنني التفكير فيه هو إيقاف الخوارزمية عند العثور على المسار ، أي كسر الدورة عندما mini = destination عندما يتم تمييزها كما تمت زيارتها.

هل هناك أي شيء آخر يمكنني فعله لجعله أفضل أم أن هذا يكفي؟

تعديل:
على الرغم من أنني أقدر الاقتراحات المقدمة لي ، إلا أن الناس ما زالوا يفشلون في الإجابة على ما سألته بالضبط. كل ما أريد معرفته هو كيفية تحسين الخوارزمية للبحث فقط عن أقصر مسار بين 2 عقد. لست مهتمًا ، في الوقت الحالي ، في جميع التحسينات العامة الأخرى. ما أقوله هو ، في خوارزمية تجد جميع أقصر المسارات من العقدة X إلى جميع العقد الأخرى ، كيف يمكنني تحسينها للبحث فقط عن مسار معين؟

ملاحظة: لقد لاحظت للتو أن for تبدأ الحلقات في 1 حتى <=, ، لماذا لا يمكن أن تبدأ في 0 واذهب حتى <?

Answer 1

يستخدم التنفيذ في سؤالك مصفوفة مجاورة ، مما يؤدي إلى تنفيذ O (n^2). بالنظر إلى أن الرسوم البيانية في العالم الواقعي عادة ما تكون متناثرة ، أي أن عدد العقد N عادة ما يكون كبيرًا جدًا ، ومع ذلك ، فإن عدد الحواف أقل بكثير من N^2.

من الأفضل أن تنظر إلى أ تنفيذ DIJKSTRA القائم على الكومة.

راجع للشغل ، لا يمكن حل أقصر مسار زوج واحد أسرع من أقصر مسار من عقدة معينة.

#include<algorithm>
using namespace std;

#define MAXN 100
#define HEAP_SIZE 100
typedef int Graph[MAXN][MAXN];

template <class COST_TYPE>
class Heap
{
public:
    int data[HEAP_SIZE],index[HEAP_SIZE],size;
    COST_TYPE cost[HEAP_SIZE];
    void shift_up(int i)
    {
        int j;
        while(i>0)
        {
            j=(i-1)/2;
            if(cost[data[i]]<cost[data[j]])
            {
                swap(index[data[i]],index[data[j]]);
                swap(data[i],data[j]);
                i=j;
            }
            else break;
        }
    }
    void shift_down(int i)
    {
        int j,k;
        while(2*i+1<size)
        {
            j=2*i+1;
            k=j+1;
            if(k<size&&cost[data[k]]<cost[data[j]]&&cost[data[k]]<cost[data[i]])
            {
                swap(index[data[k]],index[data[i]]);
                swap(data[k],data[i]);
                i=k;
            }
            else if(cost[data[j]]<cost[data[i]])
            {
                swap(index[data[j]],index[data[i]]);
                swap(data[j],data[i]);
                i=j;
            }
            else break;
        }
    }
    void init()
    {
        size=0;
        memset(index,-1,sizeof(index));
        memset(cost,-1,sizeof(cost));
    }
    bool empty()
    {
        return(size==0);
    }
    int pop()
    {
        int res=data[0];
        data[0]=data[size-1];
        index[data[0]]=0;
        size--;
        shift_down(0);
        return res;
    }
    int top()
    {
        return data[0];
    }
    void push(int x,COST_TYPE c)
    {
        if(index[x]==-1)
        {
            cost[x]=c;
            data[size]=x;
            index[x]=size;
            size++;
            shift_up(index[x]);
        }
        else
        {
            if(c<cost[x])
            {
                cost[x]=c;
                shift_up(index[x]);
                shift_down(index[x]);
            }
        }
    }
};



int Dijkstra(Graph G,int n,int s,int t)
{
    Heap<int> heap;
    heap.init();
    heap.push(s,0);
    while(!heap.empty())
    {
        int u=heap.pop();
        if(u==t)
            return heap.cost[t];
        for(int i=0;i<n;i++)
            if(G[u][i]>=0)
                heap.push(i,heap.cost[u]+G[u][i]);
    }
    return -1;
}

Answer 2

ربما يمكنك تحسين إلى حد ما عن طريق الحفاظ على قائمة منفتحة ومغلقة منفصلة (زيارتها وغير مرغوبة) قد تحسن أوقات البحث قليلاً.

تقوم حاليًا بالبحث عن عقدة غير مرغوب فيها مع أصغر مسافة إلى المصدر.

1) يمكنك الحفاظ على قائمة "مفتوحة" منفصلة ستصبح أصغر وأصغر مع تكرارك وبالتالي تجعل مساحة البحث أصغر تدريجياً.

2) إذا كنت تحتفظ بقائمة "مغلقة" (تلك العقد التي قمت بزيارتها) ، يمكنك التحقق من المسافة ضد تلك العقد فقط. سيؤدي هذا إلى زيادة مساحة البحث بشكل تدريجي ولكن لا يتعين عليك التحقق من جميع العقد كل تكرار. فحص المسافة ضد العقد التي لم تتم زيارتها حتى الآن لا يوجد غرض.

أيضًا: ربما فكر في اتباع الرسم البياني عند اختيار العقدة التالية لتقييم: في القائمة "المغلقة" ، يمكنك البحث عن أصغر مسافة ثم البحث عن عقدة "مفتوحة" بين اتصالاتها. (إذا تبين أن العقدة لا تحتوي على عقد مفتوح في اتصالاتها ، فيمكنك إزالتها من القائمة المغلقة ؛ طريق مسدود). يمكنك حتى استخدام هذا الاتصال لتشكيل قائمتك المفتوحة ، وهذا من شأنه أن يساعد في الجزر أيضًا (سيتعطل الرمز الخاص بك حاليًا إذا كان لدى الرسم البياني جزر).

يمكنك أيضًا بناء رسم بياني اتصال أكثر كفاءة بدلاً من جدول متقاطع يحتوي على جميع مجموعات العقدة الممكنة (على سبيل المثال ، بنية عقدة مع قائمة عقدة الجيران). هذا من شأنه أن يزيل الاضطرار للتحقق من جميع العقد لكل عقدة في صفيف dist [] [

بدلاً من تهيئة جميع مسافات العقدة إلى اللانهاية ، يمكنك تهيئتها إلى "أصغر مسافة متفائلة ممكنة" إلى الهدف وتفضيل معالجة العقدة بناءً على ذلك (تختلف إمكانياتك هنا ، إذا كانت العقد على مستوى ثنائي الأبعاد ، يمكنك استخدام مسافة الطيور ). انظر أوصاف* من أجل الاستدلال. لقد قمت بتطبيق هذا حول قائمة انتظار ، لست متأكدًا تمامًا من كيفية دمجه في هذا الرمز (بدون قائمة انتظار).

Answer 3

أكبر تحسن يمكنك القيام به أكثر أ* في حين أن. بالطبع ، هذا يتطلب أن يكون لديك وظيفة إرشادية.