如何为 2 个节点之间的单个最短路径优化 Dijkstra 算法? [英] How to optimize Dijkstra algorithm for a single shortest path between 2 nodes?
问题描述
我试图在 C 语言中理解 这个实现Dijkstra 算法,同时对其进行修改,以便仅找到 2 个特定节点(源和目标)之间的最短路径.
I was trying to understand this implementation in C of the Dijkstra algorithm and at the same time modify it so that only the shortest path between 2 specific nodes (source and destination) is found.
但是,我不知道到底要做什么.在我看来,没什么可做的,我似乎无法更改 d[]
或 prev[]
导致这些数组以最短的时间聚合了一些重要数据路径计算.
However, I don't know exactly what do to. The way I see it, there's nothing much to do, I can't seem to change d[]
or prev[]
cause those arrays aggregate some important data for the shortest path calculation.
我唯一能想到的就是在找到路径时停止算法,即在mini = destination
标记为已访问时打破循环.
The only thing I can think of is stopping the algorithm when the path is found, that is, break the cycle when mini = destination
when it's being marked as visited.
我还能做些什么来让它变得更好,或者就足够了吗?
Is there anything else I could do to make it better or is that enough?
虽然我很欣赏给我的建议,但人们仍然无法准确回答我提出的问题.我只想知道如何优化算法以仅搜索2 个节点之间的最短路径.目前,我对所有其他一般优化不感兴趣.我要说的是,在查找从节点 X 到所有其他节点的所有最短路径的算法中,如何优化它以仅搜索特定路径?
While I appreciate the suggestions given to me, people still fail to answer exactly what I questioned. All I want to know is how to optimize the algorithm to only search the shortest path between 2 nodes. I'm not interested, for now, in all other general optimizations. What I'm saying is, in an algorithm that finds all shortest paths from a node X to all other nodes, how do I optimize it to only search for a specific path?
PS:我刚刚注意到 for
循环从 1
开始,直到 <=
,为什么不能从 开始>0
直到 <
?
P.S: I just noticed that the for
loops start at 1
until <=
, why can't it start at 0
and go until <
?
推荐答案
您问题中的实现使用了相邻矩阵,这导致 O(n^2) 实现.考虑到现实世界中的图通常是稀疏的,即节点数 n 通常非常大,但是边数远少于 n^2.
The implementation in your question uses a adjacent matrix, which leads O(n^2) implementation. Considering that the graphs in the real world are usually sparse, i.e. the number of nodes n is usually very big, however, the number of edges is far less from n^2.
您最好查看基于堆的 dijkstra 实现.
顺便说一句,单对最短路径的求解速度不能比来自特定节点的最短路径更快.
BTW, single pair shortest path cannot be solved faster than shortest path from a specific node.
#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;
}
这篇关于如何为 2 个节点之间的单个最短路径优化 Dijkstra 算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!