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

Question

Я пытался понять эту реализацию в C алгоритма Дейкстры и в то же время изменить ее так, чтобы был найден только кратчайший путь между двумя конкретными узлами (источником и местом назначения).

Однако я точно не знаю, что с этим делать. На мой взгляд, ничего особенного не получается, кажется, я не могу изменить d[] или prev[], потому что эти массивы объединяют некоторые важные данные для вычисления кратчайшего пути.

Единственное, о чем я могу думать, это остановить алгоритм, когда путь найден, то есть прервать цикл, когда mini = destination, когда он помечен как посещенный.

Есть ли что-нибудь еще, что я мог бы сделать, чтобы сделать его лучше, или этого достаточно?

EDIT:
Хотя я ценю высказанные мне предложения, люди все равно не могут точно ответить на мои вопросы. Все, что я хочу знать, это как оптимизировать алгоритм для поиска только кратчайшего пути между 2 узлами . Мне пока не интересны все другие общие оптимизации. То, что я говорю, в алгоритме, который находит все кратчайшие пути от узла X ко всем остальным узлам, как мне оптимизировать его для поиска только определенного пути?

P.S .: Я только что заметил, что петли 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

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

Answer 3

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

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

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

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

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

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

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