寻找最短路径-dijkstra算法之CAD版（含程序）

highflybird

弄了一个 寻找最短路径-dijkstra算法之CAD版。

这个是dijkstra算法在AutoCAD上的应用。可以看出dijkstra算法效率很高。本程序采用ObjectARX编译，速度很快，代码比较简短。有探讨的朋友可联系我。
下面是演示效果：

这里提供arx程序，按CAD相应版本加载即可，命令是：DDD

（程序不再设置时间限制，也不再收取明经币，以前收取的，望见谅！）
其中核心代码是：

1. void CGraph::dijkstra(CNode& startNode)
   
2. {
   
3.   for (std::set<CNode>::iterator n = allNodes.begin(); n !=allNodes.end (); ++n)
   
4.   {
   
5.     (bool)n->bVisted = false;  // true表示到结点i的最短路径已经找到
   
6.     (double)n->dist = DBL_MAX;  // 记录所有结点到起点的距离
   
7.   }
   
8.   pre.resize(allNodes.size());
   
9.   startNode.dist = 0;        // 起点到自己的距离为0
   
10. 
    
11.   // 优先队列，存结点信息
    
12.   priority_queue<pair<double, CNode*>, vector<pair<double, CNode*>>, greater<pair<double, CNode*>>> Q;
    
13.   Q.push(make_pair(0,&startNode));// 起点入队
    
14.   while(!Q.empty())
    
15.   {
    
16.     CNode* u = Q.top().second;  // pop出距离起点s最小的节点u
    
17.     Q.pop();
    
18.     if (u->bVisted) continue;  // 丢弃已经找到最短路径的结点，即集合A中的结点
    
19.     u->bVisted = true;
    
20.     for (std::set<CEdge>::iterator e = u->edges.begin(); e != u->edges.end(); ++e)// 检查结点u的所有邻居
    
21.     {
    
22.       CNode* v = e->pNext->isEqualTo(*u,actol) ? (e->pNode) : ( e->pNext); // 邻居对应的节点
    
23.       if (v->bVisted) continue;// 丢弃已经找到最短路径的邻居结点  
    
24.       double d = e->length+u->dist;
    
25.       if (v->dist > d)
    
26.       {
    
27.         v->dist = d;
    
28.         Q.push(make_pair(d,v));// 扩展新的邻居，放到优先队列中
    
29.         pre[v->index].index = u->index ; // 记录节点
    
30.         pre[v->index].edge = *e;         // 记录路径
    
31.       }
    
32.     }
    
33.   }
    
34. }

void CGraph::dijkstra(CNode& startNode)<br /> {<br />   for (std::set<CNode>::iterator n = allNodes.begin(); n !=allNodes.end (); ++n)<br />   {<br />     (bool)n->bVisted = false;  // true表示到结点i的最短路径已经找到<br />     (double)n->dist = DBL_MAX;  // 记录所有结点到起点的距离<br />   }<br />   pre.resize(allNodes.size());<br />   startNode.dist = 0;        // 起点到自己的距离为0<br /> <br />   // 优先队列，存结点信息<br />   priority_queue<pair<double, CNode*>, vector<pair<double, CNode*>>, greater<pair<double, CNode*>>> Q;<br />   Q.push(make_pair(0,&startNode));// 起点入队<br />   while(!Q.empty())<br />   {<br />     CNode* u = Q.top().second;  // pop出距离起点s最小的节点u<br />     Q.pop();<br />     if (u->bVisted) continue;  // 丢弃已经找到最短路径的结点，即集合A中的结点<br />     u->bVisted = true;<br />     for (std::set<CEdge>::iterator e = u->edges.begin(); e != u->edges.end(); ++e)// 检查结点u的所有邻居<br />     {<br />       CNode* v = e->pNext->isEqualTo(*u,actol) ? (e->pNode) : ( e->pNext); // 邻居对应的节点<br />       if (v->bVisted) continue;// 丢弃已经找到最短路径的邻居结点  <br />       double d = e->length+u->dist;<br />       if (v->dist > d)<br />       {<br />         v->dist = d;<br />         Q.push(make_pair(d,v));// 扩展新的邻居，放到优先队列中<br />         pre[v->index].index = u->index ; // 记录节点<br />         pre[v->index].edge = *e;         // 记录路径<br />       }<br />     }<br />   }<br /> }

代码参考了：https://zhuanlan.zhihu.com/p/615138731

flowerson

要是可以变成lisp就好了 。

highflybird

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也可以并行化,嘻嘻

永不言弃

牛，就是不懂这个语言

czb203

大佬作品必属精品

dcl1214

我经常遇到下面的导航计算

Syu

学习了!
大佬作品必属精品

emk

大佬作品必属精品