寻找最短路径-dijkstra算法之CAD版

admin1

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

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

其中核心代码是

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
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. }
36. 代码参考了：https://zhuanlan.zhihu.com/p/615138731

复制代码