Как оптимизировать алгоритм Dijkstra для единственного кратчайшего пути между 2 узлами?
Я пытался понять, что эта реализация в C алгоритма Dijkstra и в то же время изменяет его так, чтобы только кратчайший путь между 2 определенными узлами (источник и место назначения) был найден.
Однако я не знаю точно, что делает к. Путем я вижу его, нет ничего особенного, чтобы сделать, я, может казаться, не изменяюсь d[] или prev[] вызовите те массивы агрегат некоторые важные данные для вычисления кратчайшего пути.
Единственная вещь, о которой я могу думать, останавливает алгоритм, когда путь найден, то есть, повредите цикл когда mini = destination когда это отмечается, как посещается.
Есть ли что-либо еще, что я мог сделать для создания его лучше или что достаточно?
Править:
В то время как я ценю предложения, данные мне, людям все еще не удается ответить точно, что я подверг сомнению. Все, что я хочу знать, - то, как оптимизировать алгоритм, чтобы только искать кратчайший путь между 2 узлами. Мне не интересно, на данный момент, во всей другой общей оптимизации. То, что я говорю, в алгоритме, который находит все кратчайшие пути от узла X ко всем другим узлам, как я оптимизирую его, чтобы только искать определенный путь?
P.S.: Я просто заметил что for циклы запускаются в 1 до <=, почему это не может запуститься в 0 и пойдите до <?
3 ответа
Реализация в вашем вопросе использует смежный матрица, которая приводит к реализации 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) Если вы ведете «закрытый» список (те узлы, которые вы посетили), вы можете проверять расстояние только по этим узлам. Это будет постепенно увеличивать пространство поиска, но вам не нужно проверять все узлы на каждой итерации. Проверка расстояния по узлам, которые еще не были посещены, не имеет смысла.
Также: возможно, подумайте о том, чтобы следовать графику при выборе следующего узла для оценки: в «закрытом» списке вы можете искать наименьшее расстояние, а затем искать «открытый» узел среди его соединений. (если выясняется, что узел не имеет открытых узлов в его соединениях, вы можете удалить его из закрытого списка; тупик). Вы даже можете использовать это соединение для формирования открытого списка, это также поможет с островами (ваш код сейчас выйдет из строя, если на вашем графике есть острова).
Вы также можете предварительно построить более эффективный граф соединений вместо перекрестной таблицы, содержащей все возможные комбинации узлов (например, структуру узла со списком узлов neighbors []).Это избавит от необходимости проверять все узлы для каждого узла в массиве dist [] []
Вместо инициализации всех узловых расстояний до бесконечности вы можете инициализировать их на «минимально возможное оптимистическое расстояние» до цели и отдать предпочтение обработке узлов на основе на этом (ваши возможности здесь различаются, если узлы находятся на 2D-плоскости, вы можете использовать расстояние до птиц). См. Описание эвристики в A *. Однажды я реализовал это вокруг очереди, не совсем уверен, как интегрировать это в этот код (без очереди).
Самое большое улучшение, которое вы можете сделать по сравнению с Дейкстрой, - это использовать вместо него A * . Конечно, для этого нужна эвристическая функция.