c++ - 我对 Dijkstra 算法的实现总是一团糟

Question

我正在为学校实现 Dijkstra 算法，但我的代码总是出错。我关注了 pseudo-code on Wikipedia很接近。我在 this form 中使用加权邻接表实现了该图所以我通过遍历相应的行来检查邻居。

这是我的图形类，以及我的顶点结构。

struct vertex
{
    //constructor
    vertex(size_t d_arg, size_t n_arg)
    {
        n = n_arg;
        d = d_arg;
    }

    //member variables, n is name and d is distance
    size_t n;
    size_t d;

    //overloaded operator so I can use std::sort in my priority queue
    bool operator<(const vertex& rhs) const
    {
        return  d<rhs.d;
    }

};

class graph
{
public:
    graph(vector<vector<size_t> > v){ ed = v;};
    vector<size_t> dijkstra(size_t src);
    bool dfs(size_t src);
private:
    //stores my matrix describing the graph
    vector<vector<size_t> > ed;
};

函数 dfs 实现深度优先搜索来检查图是否连接。我对此没有任何问题。但是 dijkstra 函数给了我错误的值。这是它的实现方式。

vector<size_t> graph::dijkstra(size_t src)
{
    //a vector storing the distances to the vertices and a priority queue
    vector<size_t> dist;
    dist[src] = 0;
    p_q<vertex> q;

    //set the distance for the vertices to inphinity, since they're size_t and -1 is largest
    for (size_t i = 0; i < ed.size(); i++) {
        if(i!=src)
        {
            dist.push_back(-1);
        }

        //push the vertices to the priority queue
        vertex node(dist[i], i);
        q.push(node);
    }

    //while there's stuff in the queue
    while(q.size())
    {
        //c, the current vertex, becomes the top
        vertex c = q.pop();

        //iterating through all the neighbours, listed in the adjacency matrix
        for(int i = 0; i < ed[0].size(); i++)
        {
            //alternative distance to i is distance to current and distance between current and i
            size_t alt = dist[c.n] + ed[c.n][i];

            //if we've found a better distance
            if(alt < dist[i])
            {
                //new distance is alternative distance, and it's pushed into the priority queue
                dist[i] = alt;
                vertex n(alt, i);
                q.push(n);
            }

        }
    }

    return dist;
}

我不明白我为什么遇到麻烦。我用这个矩阵调试过。

 0  3 -1  1 
 3  0  4  1 
-1  4  0 -1 
 1  1 -1  0

除了顶点 0 和顶点 3，它没有访问任何东西。

Answer 1

其中一个问题就在 graph::dijkstra 的开头，当分配零大小数组的元素时:

vector<size_t> dist;
dist[src] = 0;

在伪代码中可以，但在 C++ 中不行。或许你可以这样改:

vector<size_t> dist;
for (size_t i = 0; i < ed.size(); i++) {
    if(i!=src)
    {
        dist.push_back(-1);
    }
    else
    {
        dist.push_back(0);
    }
    ....