Как оптимизировать алгоритм Дейкстры для одного кратчайшего пути между двумя узлами?

Реализация в вашем вопросе использует соседнюю матрицу, что приводит к реализации 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;
}

Возможно, вы могли бы несколько улучшить, поддерживая отдельные открытые и закрытые списки (посещенные и непосещенные), это может немного улучшить время поиска.

В настоящее время вы ищете непосещенный узел с наименьшим расстоянием до источника.

1) Вы можете поддерживать отдельный «открытый» список, который будет становиться все меньше и меньше по мере повторения и, таким образом, постепенно уменьшая пространство поиска.

2) Если вы поддерживаете «закрытый» список (те узлы, которые вы посетили), вы можете проверить расстояние только для этих узлов. Это будет постепенно увеличивать ваше пространство поиска, но вам не нужно проверять все узлы на каждой итерации. Проверка расстояния по узлам, которые еще не были посещены, не имеет смысла.

Кроме того: возможно, следует рассмотреть график при выборе следующего узла для оценки: в «закрытом» списке вы можете искать наименьшее расстояние, а затем искать «открытый» узел среди его соединений. (если узел не имеет открытых узлов в своих соединениях, вы можете удалить его из закрытого списка; тупик). Вы даже можете использовать это подключение для формирования открытого списка, это также поможет с островами (ваш код в настоящее время будет аварийно завершать работу, если на вашем графике есть острова).

Вы также можете предварительно построить более эффективный граф соединений вместо кросс-таблицы, содержащей все возможные комбинации узлов (например, структуру узла со списком узлов соседей []). Это избавит вас от необходимости проверять все узлы для каждого узла в массиве dist[][]

Вместо того, чтобы инициализировать все расстояния узлов до бесконечности, вы можете инициализировать их до «наименьшего возможного оптимистического расстояния» до цели и предпочесть обработку узлов на основе этого (здесь ваши возможности различаются, если узлы находятся на 2D-плоскости, вы можете использовать расстояние от птицы ). См. описания A* для эвристики. Однажды я реализовал это вокруг очереди, не совсем уверенный, как бы я интегрировал это в этот код (то есть без очереди).

Самое большое улучшение, которое вы можете сделать по сравнению с Дейкстрой, — это использовать вместо него A*. Конечно, для этого требуется наличие эвристической функции.