如何针对2个节点之间的单个最短路径优化Dijkstra算法?
我试图在Dijkstra算法的C中理解这个实现 ,同时修改它,以便只找到2个特定节点(源和目的地)之间的最短路径。
但是,我不确切知道该做些什么。 我看到它的方式,没有什么可做的,我似乎无法改变d[]
或prev[]
因为这些数组聚合了一些重要数据用于最短路径计算。
我唯一能想到的就是在找到路径时停止算法,也就是说,当mini = destination
被标记为已访问时,打破循环。
还有什么我可以做的让它变得更好还是够了?
编辑:
虽然我很欣赏给予我的建议,但人们仍未能完全回答我的质疑。 我想知道的是如何优化算法以仅搜索2个节点之间的最短路径。 到目前为止,我对所有其他一般优化都不感兴趣。 我所说的是,在找到从节点X到所有其他节点的所有最短路径的算法中,如何优化它以仅搜索特定路径?
PS:我刚注意到for
循环从1
开始直到<=
,为什么它不能从0
开始直到<
?
您的问题中的实现使用相邻矩阵,这导致O(n ^ 2)实现。 考虑到现实世界中的图形通常是稀疏的,即节点数n通常非常大,但是边缘的数量远小于n ^ 2。
你最好看一下基于堆的dijkstra实现 。
BTW,单对最短路径不能比特定节点的最短路径更快地解决。
#include using namespace std; #define MAXN 100 #define HEAP_SIZE 100 typedef int Graph[MAXN][MAXN]; template 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]] 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=0) heap.push(i,heap.cost[u]+G[u][i]); } return -1; }
通过维护一个单独的打开和关闭列表(访问和未访问)可能会有所改善,它可以稍微改善寻道时间。
目前,您搜索距离源最小的未访问节点。
1)您可以维护一个单独的“打开”列表,在迭代时会越来越小,从而使搜索空间逐渐变小。
2)如果您维护一个“关闭”列表(您访问过的那些节点),您可以仅检查那些节点的距离。 这将逐步增加您的搜索空间,但您不必每次迭代都检查所有节点。 对尚未访问过的节点的距离检查没有任何意义。
另外:在选择要评估的下一个节点时,可能会考虑遵循图表:在“关闭”列表中,您可以寻找最小距离,然后在其连接中搜索“打开”节点。 (如果节点在其连接中没有打开的节点,则可以将其从关闭列表中删除;死胡同)。 你甚至可以使用这种连接形成你的开放列表,这也有助于岛屿(如果你的图表有岛屿,你的代码将会崩溃)。
您还可以预先构建更高效的连接图,而不是包含所有可能节点组合的交叉表(例如,具有neighbors []节点列表的Node结构)。 这将删除必须检查dist [] []数组中每个节点的所有节点
不是将所有节点距离初始化为无穷大,而是可以将它们初始化为目标的“最小可能的乐观距离”,并基于此优先于节点处理(这里的可能性不同,如果节点在2D平面上,则可以使用鸟距离)。 请参阅启发式的A *描述。 我曾经在一个队列周围实现这个,不完全确定如何将它集成到这个代码中(没有队列)。
您可以对Dijkstra进行的最大改进是使用A * 。 当然,这要求您具有启发式function。