大佬教程收集整理的这篇文章主要介绍了dijkstra的算法 – 在c?,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
vector<int> dijkstra(costMatrix[][]) { .... .... return vector<int>pathPoinTindex } main() { vector<Point> availablePoints; costMatrix[][]=createCostMatrix(); vector<int> indexes=dijikstra(costMatriX) for(int i=0;i<indexes.size();i++) cout << "path points are " << availablePoints[indexes[i]] << endl; }
如果有人,你可以发贴代码.我不懒.但是我的项目一天前已经超过了截止日期.现在我失去了理解逻辑的希望.现在只是我想要的功能. “有需要的人是天使”.
编辑:特别感谢“Loki astari”的出色答案
您可以找到体面的完整实现here.您将必须添加路径向量并实现RecoverPath方法,以便从源到宿的路径上获取节点.要使用此@L_489_12@案,还需要以下列方式将邻接矩阵转换为邻接列表:
for (int i=0;i<nNodes;i++) for (int j=0;j<nNodes;j++){ if (costMatrix[i][j] != NO_EDGE_value){ G[i].pb(make_pair(j,costMatrix[i],[j])); } }
编辑:如果你的图形很密集,我建议你使用Ford Bellman算法要简单得多,不要太慢.
int P[MAX]; /*array with links to parents*/ for(i=0; i<=nodes; i++) P[i] = -1; /*magic unset value*/ // dijkstra while(!Q.empty()) { .... if(!F[v] && D[u]+w < D[v]) { D[v] = D[u] + w; /*By setTing P[v] value we will remember what is the prevIoUs node on path from source */ P[v] = u; // <-- added line Q.push(pii(v,D[v])); } ... }
那么你必须添加RecoverPath方法(仅当路径存在时才有效)
vector<int> RecoverPath(int src,int dest){ vector<int> path; int v = dest; while (v != srC) { path.push_BACk(v); v = P[v]; } path.push_BACk(src); std::reverse(path.begin(),path.end()); return path; }
以上是大佬教程为你收集整理的dijkstra的算法 – 在c?全部内容,希望文章能够帮你解决dijkstra的算法 – 在c?所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。