dijkstra 的算法 - 在 C++ 中？

dijkstra's algorithm - in c++?

提问by prabhakaran

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

在过去的四天里，我试图理解 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;
}

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" .

如果有人，请您发布代码。我不懒惰。但是我的项目一天前已经过了截止日期。现在我失去了理解逻辑的希望。现在只是我想要这个功能。“有需要的人确实是天使”。

EDIT:Special thanks to "Loki astari" for his excellent answer

编辑：特别感谢“Loki astari”的出色回答

采纳答案by jethro

I advise you to look at TopCodertutorial 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 weightsin your graph.

我建议您查看具有非常实用的方法的TopCoder教程。您需要了解 STL 优先级队列是如何工作的，并确保您negative edge weights的图中没有任何优先级队列。

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

体面的完整实现可以在这里找到。您必须向其添加路径向量并实现RecoverPath方法，以便在从源到接收器的路径上获取节点。要使用此解决方案，您还需要通过以下方式将您的转换adjacency matrix为adjacency list：

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

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

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

EDIT2: To calculate path you should add in the header

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

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

然后你必须添加 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;
}

回答by Martin York

Dijkstra's algorithm

Dijkstra 算法

用英语：

This is an algorithm for finding the shortest route from point A to point B.
In computing terms we simplify the route to a graph consisting of nodes and arcs. Each node represents an intermediate point while each arc connect two nodes and has a (non negative) weight representing the cost to traverse between the two nodes.

这是一种寻找从 A 点到 B 点的最短路线的算法。
在计算方面，我们将路线简化为由节点和弧组成的图形。每个节点代表一个中间点，而每条弧线连接两个节点并具有（非负）权重，代表在两个节点之间遍历的成本。

To implement the algorithm you need two lists:

要实现该算法，您需要两个列表：

• finished: A set of (node,cost) where you have computed the minimum cost to reach.
• working: A sorted list of (node,cost) that have been checked.

• 完成：一组（节点，成本），您已经计算了要达到的最低成本。
• 工作：已检查的（节点，成本）的排序列表。

Algorithm:

算法：

working.addNode(Start, 0); // No cost to get to start.

for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
    // If we have already processed this node ignore it.
    if (finished.find(node))
    {    continue;
    }

    // We have just removed a node from working.
    // Because it is the top of the list it is guaranteed to be the shortest route to
    // the node. If there is another route to the node it must go through one of the
    // other nodes in the working list which means the cost to reach it will be higher
    // (because working is sorted). Thus we have found the shortest route to the node.

    // As we have found the shortest route to the node save it in finished.
    finished.addNode(node,cost);

    // For each arc leading from this node we need to find where we can get to.
    foreach(arc in node.arcs())
    {
        dest = arc.dest();
        if (NOT (finished.find(dest)))
        {
            // If the node is already in finished then we don't need to worry about it
            // as that will be the shortest route other wise calculate the cost and add
            // this new node to the working list.
            destCost = arc.cost() + cost;
            working.addNode(dest,destCost); // Note. Working is sorted list
        }
    }
} 

So if you think about this algorithm. Say you are traveling from London to Manchester.

所以如果你考虑一下这个算法。假设您从伦敦前往曼彻斯特。

finished = {} // empty.
working  = { (London,0) }

Using the following Costs matrix:

使用以下成本矩阵：

                  L    S    O    B    N    M    W
(L) ondon         -    50   60   100  130  -    -
(S) outhampton    50   -    70   -    -    -    -
(O) xford         60   70   -    50   -    200  -
(B) irmingham     100  -    50   -    -    80   110
(N) orwich        130  -    -    -    -    -    -
(M) anchester     -    -    200  80   -    -    80
Ne(W) castle      -    -    -    110  -    80   -

Now you take London out of the working list (as it is at the head) and place it into the finished list. Then add to the working list all the towns directly connected to London.

现在，您将伦敦从工作列表中删除（因为它位于开头）并将其放入完成的列表中。然后将所有与伦敦直接相连的城镇添加到工作列表中。

finished = { (London,0) }
working  = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }

Consider the towns in the working set the outer edge of a bubble that has expanded from London. The job of Dijkstra's algorithm is to keep expanding the bubble until we hit Manchester (without retracing any steps we have already taken). So the bubble always expands outwards and we always expand the part of the bubble that is smallest.

考虑工作集中的城镇是从伦敦扩张的泡沫的外缘。Dijkstra 算法的工作是不断扩大泡沫，直到我们击中曼彻斯特（不回溯我们已经采取的任何步骤）。所以泡沫总是向外膨胀，我们总是扩大泡沫中最小的部分。

So the next step is to take the head of the list and repeat. From Southampton there are only two destinations. Back to London (which we discard as it is in the finished list) and Oxford. The cost to get to Oxford is 50 + the cost from Southampton to Oxford (so notice it is in the working list twice but don;t worry we will discard it later as not an optimal route).

所以下一步是取列表的头部并重复。从南安普敦只有两个目的地。回到伦敦（我们在完成的列表中丢弃了它）和牛津。去牛津的费用是 50 + 从南安普敦到牛津的费用（所以请注意它在工作列表中两次，但不要担心我们稍后会因为不是最佳路线而丢弃它）。

finished = { (London,0), (Southampton,50) }
working  = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }

So repeat the loop. The head of the list is Oxford. From Oxford we can go to Manchester(200), Birmingham(50) or back to London(60) or Southampton(Remember we need to add the cost of getting to oxford to each of these costs above. Note that from Oxford we could have gone to Southampton but we have already found the shortest route to Southampton so no processing is required) This will leave us with:

所以重复循环。榜首是牛津大学。从牛津我们可以去曼彻斯特（200）、伯明翰（50）或回到伦敦（60）或南安普顿（请记住，我们需要将前往牛津的费用加到上述每一项费用中。注意，从牛津我们可以有去了南安普敦，但我们已经找到了到南安普敦的最短路线，因此不需要处理）这将留给我们：

finished = { (London,0), (Southampton,50), (Oxford, 60) }
working  = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}

Notice we have Manchester in the working list now (this is our destination). But we need to keep working as we may find a shorter route. So now we expand from Birmingham. From there we can go to Oxford(50), Manchester(80), London(100), Newcastle(110). Adding the cost of getting to Birmingham in the first place this gives us:

请注意，我们现在在工作列表中有曼彻斯特（这是我们的目的地）。但是我们需要继续努力，因为我们可能会找到一条更短的路线。所以现在我们从伯明翰扩展。从那里我们可以去牛津（50）、曼彻斯特（80）、伦敦（100）、纽卡斯尔（110）。首先加上去伯明翰的费用，这给了我们：

finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working  = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}

The next two nodes. Oxford and Birmingham are already in the finished list so we can ignore them. So unless there is a route from Norwich to Manchester that is less than 50 miles we will reach Manchester in the iteration after that.

接下来的两个节点。牛津和伯明翰已经在完成的名单中，所以我们可以忽略它们。因此，除非有一条从诺维奇到曼彻斯特的路线少于 50 英里，否则我们将在此后的迭代中到达曼彻斯特。

回答by Samuel

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <limits> 
#include <set>
#include <utility>
#include <algorithm> 
#include <iterator>

using namespace std;


typedef int vertex_t;
typedef double weight_t;

const weight_t max_weight = numeric_limits<double>::infinity();

struct neighbor {
    vertex_t target;
    weight_t weight;
    neighbor(vertex_t arg_target, weight_t arg_weight)
        : target(arg_target), weight(arg_weight) { }
};

typedef vector<vector<neighbor> > adjacency_list_t;

// Computing the shortest pathway

void
DijkstraComputePaths(vertex_t source,
                     const adjacency_list_t &adjacency_list,
                     vector<weight_t> &min_distance,
                     vector<vertex_t> &previous)
{
    int n = adjacency_list.size();
    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;
    previous.clear();
    previous.resize(n, -1);
    set<pair<weight_t, vertex_t> > vertex_queue;
    vertex_queue.insert(make_pair(min_distance[source], source));

    while (!vertex_queue.empty())
    {
        weight_t dist = vertex_queue.begin()->first;
        vertex_t u = vertex_queue.begin()->second;
        vertex_queue.erase(vertex_queue.begin());

        // Visit each edge exiting u
        const vector<neighbor> &neighbors = adjacency_list[u];
        for (vector<neighbor>::const_iterator neighbor_iter = neighbors.begin();
            neighbor_iter != neighbors.end();
            neighbor_iter++)
        {
            vertex_t v = neighbor_iter->target;
            weight_t weight = neighbor_iter->weight;
            weight_t distance_through_u = dist + weight;
            if (distance_through_u < min_distance[v]) {
                vertex_queue.erase(make_pair(min_distance[v], v));

                min_distance[v] = distance_through_u;
                previous[v] = u;
                vertex_queue.insert(make_pair(min_distance[v], v));

            }
        }
    } // while
}

回答by Sergey Vystoropskyi

The main idea of Dijkstra algorithm is rather simple: Suppose you have a set of points with a known shortest paths to a given point A. Then lets assume we want to add a new point C to a set. Lets find which points from the set are connected with a point we want to add. Let it be point's B(i) So for all point's B(i) we will new to find a sum of distance between A to B(i) and B(i) and C. The smallest of that distances will be the minimum between A and C.

Dijkstra 算法的主要思想相当简单：假设您有一组点，这些点具有到给定点 A 的已知最短路径。然后假设我们要向集合中添加一个新点 C。让我们找出集合中的哪些点与我们要添加的点相连。让它成为点的 B(i) 所以对于所有点的 B(i)，我们将新找到 A 到 B(i) 和 B(i) 和 C 之间的距离之和。最小的距离将是两者之间的最小值A 和 C。

回答by Teodor Pripoae

Implementation in c ++

在 C++ 中的实现

#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.insert( mp(0, 1) );

    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
            d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
    }
}

int main(void)
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int i, a, b, c;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= M; i++)
        scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);

    solve();

    for(i = 2; i <= N; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}

回答by ???? ????

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>


using namespace std;

const size_t INT_MAX = 0xFFFFFFFF; // or any other value representing infinite distance.

first create a struct edge containing the source node index, destination node index and the edge "weight"( length ).

首先创建一个包含源节点索引、目标节点索引和边“权重”（长度）的结构边。

struct edge { size_t from; size_t to; size_t length; };

define a class Node containing edges to adjacent neighbors.

定义一个包含到相邻邻居的边的类节点。

class Node 
{ 
public:
    void AddNeighborEdge( edge _NeighborEdge ) { m_neighborsEdges.push_back( _NeighborEdge ); } 
    vector<edge>::iterator FirstNeighborEdge() { return  m_neighborsEdges.begin(); }
    vector<edge>::iterator LastNeighborEdge() { return  m_neighborsEdges.end(); }

private: 
     vector<edge>  m_neighborsEdges; 
};

class NeighborsDistanceUpdator would be used as a "functor" by the for_each algorithm, for iterative pass and update of min distance from current node in the graph to adjacent neighbors.

类 NeighborsDistanceUpdator 将被 for_each 算法用作“函子”，用于迭代传递和更新图中当前节点到相邻邻居的最小距离。

class NeighborsDistanceUpdator
{
public:
    NeighborsDistanceUpdator( vector<size_t>& _min_distance_from_source, queue< size_t >& _nodes_to_visit ) : m_min_distance_from_source( _min_distance_from_source ),                                                              m_nodes_to_visit( _nodes_to_visit ) 
                                                            {} 
    void operator()( edge& _edge )
    {   
        size_t from = _edge.from;
        size_t to = _edge.to;

        if ( m_min_distance_from_source[ to ] > m_min_distance_from_source[ from ] + _edge.length ) 
        {
            m_min_distance_from_source[ to ] = m_min_distance_from_source[ from ] + _edge.length;
            m_nodes_to_visit.push( to );
        }
    }    

private:
    vector<size_t>& m_min_distance_from_source;
    queue< size_t >& m_nodes_to_visit;
};

as for the dijkstra algorithm, just run over all nodes in the graph and for each node update the min distance from source ( if less ), while saving adjacent nodes to visit.

至于 dijkstra 算法，只需遍历图中的所有节点，并为每个节点更新与源的最小距离（如果小于），同时保存相邻节点以供访问。

size_t dijkstra( map< size_t, Node  >& _graph, size_t _sourceIndex, size_t _targetIndex ) 
{
    vector<size_t> min_distance_from_source( _graph.size(), INT_MAX );
    min_distance_from_source[ _sourceIndex ] = 0;
    queue< size_t > nodes_to_visit;
    nodes_to_visit.push( _sourceIndex );
    NeighborsDistanceUpdator neighborsDistanceUpdator( min_distance_from_source, nodes_to_visit );

    while ( ! nodes_to_visit.empty() ) 
    {

        size_t currNodeIndex = nodes_to_visit.front();

        if ( currNodeIndex ==  _targetIndex ) return min_distance_from_source[ currNodeIndex ];

        nodes_to_visit.pop();

        vector<edge>::iterator firstNeighborEdge= _graph[ currNodeIndex ].FirstNeighborEdge();
        vector<edge>::iterator lastNeighborEdge= _graph[ currNodeIndex ].LastNeighborEdge();

        for_each( firstNeighborEdge, lastNeighborEdge, neighborsDistanceUpdator );
    }
    return INT_MAX;
}

test...

测试...

int main()
{
    Node node1;
    Node node2;
    Node node3;
    Node node4;

    map< size_t, Node > graph;
    edge ed;

    ed.from = 0;
    ed.to = 1;
    ed.length = 1;
    node1.AddNeighborEdge( ed );

    cout << "node: " << 0 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 0;        
    ed.to = 2;
    ed.length = 4;
    node1.AddNeighborEdge( ed );
    graph.insert( make_pair( 0, node1 ) );

    cout << "node: " << 0 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 1;
    ed.to = 2;
    ed.length = 1;
    node2.AddNeighborEdge( ed );

    cout << "node: " << 1 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 1;
    ed.to = 3;
    ed.length = 3;
    node2.AddNeighborEdge( ed );
    graph.insert( make_pair( 1, node2 ) );

    cout << "node: " << 1 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 2;
    ed.to = 3;
    ed.length = 1;
    node3.AddNeighborEdge( ed );
    graph.insert( make_pair( 2, node3 ) );

    cout << "node: " << 2 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;

    ed.from = 3;
    ed.to = INT_MAX;
    ed.length = INT_MAX;
    node3.AddNeighborEdge( ed );
    graph.insert( make_pair( 3, node4 ) );

    cout << "node: " << 2 << " to: " << ed.to ;
    cout << " lenth: " << ed.length << endl << endl;


    cout << "min length from: 1 to 4 = " << dijkstra( graph, 0,3  ) << endl;
}