Dijkstra算法 - 在C ++？ [英] dijkstra's algorithm - in c++?

问题描述

在过去的四天，我试图了解Dijkstra算法。但我不能。我有一个点的向量。从我创建了一个成本矩阵。但我不知道如何使Dijkstra算法。来源是净可用，但我不从计算机科学的背景，所以我无法理解他们。我试图做这样的功能

for the past four days I am trying to understand the dijkstra's algorithm. But I can't. I have a vector of points. From that I created a cost matrix. But I don't know how to make the dijkstra's algorithm. Sources are available in net, but I am not from Computer science background, So I can't understand them. I am trying to make a function like this

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

如果任何人，你能请张贴code。我不懒。但是，我的项目已经前一天穿过的最后期限。现在，我失去了我的希望，了解逻辑。现在只要我想要的功能。 一个人需要的是天使的确。

If anybody, can you please post the code. I am not lazy. But my project already crossed the deadline one day ago. Now I lost my hope to understand the logic. Now Just I want the function. "A man in need is the angel indeed" .

编辑：特别感谢洛基阿斯塔里为他的出色答卷。

Special thanks to "Loki astari" for his excellent answer

推荐答案

我劝你看看<一href="http://www.top$c$cr.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs3">Top$c$cr教程，有非常务实的apporach。 你需要了解如何STL优先级队列的工作，并确保你没有在你的图中的任何负边权。

I advise you to look at TopCoder tutorial that have very pragmatic apporach. You will need to find out how STL priority queue works and make sure you don't have any negative edge weights in your graph.

体面全面实施可以在这里找到 。你将不得不为了从源头上汇获得的路径节点的路径载体添加到它和实施 RecoverPath 方法。要使用此解决方案，您还需要你的邻接矩阵转换为邻接表以下列方式：

Decent full implementation can be found here. You will have to add Path vector to it and implement RecoverPath method in order to get nodes on path from source to sink. To use this solution you will also need to convert your adjacency matrix to adjacency list in following way:

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

编辑：如果你的图形是密集的我会建议你使用福特贝尔曼算法更简单，不应该是慢得多。

If your graph is dense I would advise you to use Ford Bellman algorithm is much simpler and shouldn't be much slower.

EDIT2：要计算路径，你应该添加在头

To calculate path you should add in the header

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方法（它的工作原理，只有当存在路径）

Then you have to add RecoverPath method (it works only when path exists)

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 ++？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！