Dijkstra算法

Question

Dijkstra算法 - 用C++实现？

13

过去四天我一直在尝试理解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"提供的出色答案。

- prabhakaran

1

你是否了解实际的算法本身 - 是C++让你感到困惑吗？如果你不知道算法，阅读wikipedia页面可能会有所帮助；特别是pseudo-code部分。 - Stephen

尝试将算法分成若干部分，然后再试着将它们组合在一起。迪杰斯特拉算法在一开始可能很难。仅仅询问完整的代码可能最终并没有太大帮助。 - user373455

2

我就是不明白为什么很多好的问题会被关闭，而像这样只是要求粘贴代码的问题却能得到10个赞。 - lisyarus

6个回答

13

我建议你看一下TopCoder的教程，这个教程非常实用。

你需要了解STL优先队列的工作原理，并确保你的图中没有任何负边权。

你可以在这里找到一个不错的完整实现。你需要添加路径向量并实现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算法，它更简单，速度也不会慢多少。

编辑2：要计算路径，你应该在头部添加：

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

- jethro

在上面的链接中，哪个是矩阵的行、列和值，例如matrix[row][column]=value。 - prabhakaran

在这个实现中，你有一个 vector<pii> G[MAX] 替代了 costMatrix，其中 G[x] 保存了节点 x 的出边。因此，要获取 matrix[row][col] 的值，你需要在 G[row] 中搜索 col 的值并返回其代价。 - jethro

非常感谢提供的链接，它有效了。但是我只得到了从源节点到其他节点的距离。请问如何以vector<vector<int>>的形式获取这些路径中对应的节点编号？ - prabhakaran

5

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

- Samuel

欢迎新加入者。请查看问题的日期。 - prabhakaran

6

在未来，你的回答可能会帮助到别人，也可能会对自己有所帮助。正如已经发生在那些回来寻找自己答案的人身上的一样，现在添加答案永远不会太晚。 - Emile Bergeron

2

Dijkstra算法的主要思想非常简单：假设您有一个点集，其中包含到给定点A的已知最短路径。然后假设我们想要将一个新的点C添加到该集合中。让我们找出与我们想要添加的点连接的点。假设是点B（i）。因此，对于所有点B（i），我们需要找到从A到B（i）和B（i）到C的距离之和。那些距离中最小的就是A和C之间的最小距离。

- Sergey Vystoropskyi

1

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

- Teodor Pripoae

6

我会点赞这个，但变量的命名太糟糕了。这几乎是混淆代码。 - Nic Foster

0

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

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

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

定义一个包含指向相邻节点的边的Node类。

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

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

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

测试...

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

- דרור זוהר

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin York · Accepted Answer

这是一种用于找出从点A到点B的最短路径的算法。
在计算机术语中，我们将路径简化为由节点和连线组成的图。每个节点代表一个中间点，而每个连线连接两个节点，并具有表示穿越这两个节点的成本（非负）的权值。

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

finished：一组(node, cost)，其中您已经计算出到达的最小成本。
working：已经检查过的(node, cost)的排序列表。

算法:

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

如果你想了解这个算法。假设你正在从伦敦前往曼彻斯特。

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

使用以下成本矩阵：

                  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   -

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

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

考虑工作集中的城镇是从伦敦扩展出来的泡沫的外边缘。Dijkstra算法的任务是不断扩大泡沫，直到我们到达曼彻斯特（不重复走已经走过的步骤）。所以泡沫总是向外扩展，我们总是扩展最小部分的泡沫。

所以下一步是取列表的头并重复。从南安普敦只有两个目的地。回到伦敦（我们将其丢弃，因为它在完成的列表中）和牛津。到达牛津的成本是50加上从南安普敦到牛津的成本（请注意，它在工作列表中出现了两次，但不要担心，我们将在后面将其丢弃，因为它不是最优路线）。

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

重复循环。列表的头部是牛津。从牛津我们可以前往曼彻斯特（200），伯明翰（50）或返回伦敦（60）或南安普顿（请记住，我们需要将到达牛津的费用添加到上述每个费用中。请注意，从牛津我们本可以去南安普顿，但我们已经找到了到南安普顿的最短路径，因此不需要处理）这将使我们得到：

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

请注意，我们现在的工作列表中有曼彻斯特（这是我们的目的地）。但我们需要继续努力，因为可能会找到更短的路线。所以现在我们从伯明翰开始扩展。从那里我们可以去牛津（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)}

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