dijkstra的算法 – 在c？

发布时间：2020-12-16 05:51:56 所属栏目：百科来源：网络整理

导读：在过去四天中,我正在努力了解dijkstra的算法.但我不能.我有一个积分的向量.从那我创建了一个成本矩阵.但我不知道如何使dijkstra的算法.资料来源可以在网上,但我不是从计算机科学的背景,所以我不明白他们.我试图做这样的功能 vectorint dijkstra(costMatrix[]

在过去四天中,我正在努力了解dijkstra的算法.但我不能.我有一个积分的向量.从那我创建了一个成本矩阵.但我不知道如何使dijkstra的算法.资料来源可以在网上,但我不是从计算机科学的背景,所以我不明白他们.我试图做这样的功能

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”的出色答案

解决方法

我建议你看看具有非常务实的apporach的 TopCoder教程.
您将需要了解STL优先级队列的工作原理,并确保您的图表中没有任何负边缘权重.

您可以找到体面的完整实现here.您将必须添加路径向量并实现RecoverPath方法,以便从源到宿的路径上获取节点.要使用此解决方案,还需要以下列方式将邻接矩阵转换为邻接列表：

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算法要简单得多,不要太慢.

EDIT2：要计算路径,您应该添加到标题中

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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!