寻找最短路径-dijkstra算法之CAD版（含程序）
本帖最后由 highflybird 于 2024-9-13 08:38 编辑弄了一个 寻找最短路径-dijkstra算法之CAD版。
这个是dijkstra算法在AutoCAD上的应用。可以看出dijkstra算法效率很高。本程序采用ObjectARX编译，速度很快，代码比较简短。有探讨的朋友可联系我。
下面是演示效果：
https://www.bilibili.com/video/BV1CyuXeGEzz
这里提供arx程序，按CAD相应版本加载即可，命令是：DDD
（程序不再设置时间限制，也不再收取明经币，以前收取的，望见谅！）
其中核心代码是：
void CGraph::dijkstra(CNode& startNode)
{
for (std::set<CNode>::iterator n = allNodes.begin(); n !=allNodes.end (); ++n)
{
(bool)n->bVisted = false;// true表示到结点i的最短路径已经找到
(double)n->dist = DBL_MAX;// 记录所有结点到起点的距离
}
pre.resize(allNodes.size());
startNode.dist = 0; // 起点到自己的距离为0
// 优先队列，存结点信息
priority_queue<pair<double, CNode*>, vector<pair<double, CNode*>>, greater<pair<double, CNode*>>> Q;
Q.push(make_pair(0,&startNode));// 起点入队
while(!Q.empty())
{
CNode* u = Q.top().second;// pop出距离起点s最小的节点u
Q.pop();
if (u->bVisted) continue;// 丢弃已经找到最短路径的结点，即集合A中的结点
u->bVisted = true;
for (std::set<CEdge>::iterator e = u->edges.begin(); e != u->edges.end(); ++e)// 检查结点u的所有邻居
{
CNode* v = e->pNext->isEqualTo(*u,actol) ? (e->pNode) : ( e->pNext); // 邻居对应的节点
if (v->bVisted) continue;// 丢弃已经找到最短路径的邻居结点
double d = e->length+u->dist;
if (v->dist > d)
{
v->dist = d;
Q.push(make_pair(d,v));// 扩展新的邻居，放到优先队列中
pre.index = u->index ; // 记录节点
pre.edge = *e; // 记录路径
}
}
}
}
代码参考了：https://zhuanlan.zhihu.com/p/615138731
要是可以变成lisp就好了 。 A星算法不太了解，但据：路径规划之 A* 算法 - 知乎 (zhihu.com)
里面介绍，
上面已经提到，启发函数会影响A*算法的行为。
[*]在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。
[*]如果h(n)始终小于等于节点n到终点的代价，则A*算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
[*]如果h(n)完全等于节点n到终点的代价，则A*算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。
[*]如果h(n)的值比节点n到终点的代价要大，则A*算法不能保证找到最短路径，不过此时会很快。
[*]在另外一个极端情况下，如果h()n相较于g(n)大很多，则此时只有h(n)产生效果，这也就变成了最佳优先搜索。
似乎A*算法可能不准确？
如果要用到Dijkstra的并行算，估计图形数据量很大吧。
是的,很多时候并不需要最近,而是需要最快,距离差不多就行.
并行化的作用是工程化实现,通过数据量自适应速度,
当算法无解的时候就找找硬件加速方案,嘻嘻 Astar会比它快,而且dijkstra也可以并行化,嘻嘻 牛，就是不懂这个语言
大佬作品必属精品 我经常遇到下面的导航计算 学习了!
大佬作品必属精品 大佬作品必属精品:lol:lol
页:
[1]
2