Dijkstra 算法中的分段错误

Question

我正在编写一个 c++ 程序来编写 dijkstra 算法的代码。这是代码。

#include <iostream>
#include <vector>
#include <map>
using namespace std;
class vertex;
class node
{
public:
int value;
//bool exp=false;
char c;
};
class edge
{
public:
    vertex* head;
    vertex* tail;
    int length;
    edge(vertex*h,vertex* t, int l)
    {
        head=h;
        tail=t;
        length=l;
    }
};
class vertex:public node
{
public:
    vector<edge*> a;
    vertex& operator|(vertex &p)
    {
        int l;
        cout<<"Give the length of edge "<<this->c<<p.c<<endl;
        cin>>l;
        edge q(&p,this,l);
        a.push_back(&q);
    }
    vertex(char a)
    {
        c=a;
    }
};
int main()
{
    vertex e('e');
    vertex d('d');
    vertex b('b');
    vertex c('c');
    vertex a('a');
    vertex s('s');
    s.value=1;
    a.value=2;
    b.value=3;
    c.value=4;
    d.value=5;
    e.value=6;
    s|a;
    s|b;
    a|c;
    b|c;    
    b|d;
    c|d;
    c|e;
    d|e;
    cout<<"4";
    map <char ,int >A;
    vector<edge*>::iterator minin;
    vector<edge*>::iterator j;
    int min=0;
    vector<vertex*> X;
    X.push_back(&s);
    A['s']=0;
    vector<vertex*>::iterator i=X.begin();
    for(; i<X.end(); i++)
    {
        cout<<"1";
        j=((*i)->a).begin();
        for(; j<((*i)->a).end(); j++)
        {
            cout<<"2";
            if((*j)->length+A[((*j)->tail)->c]>min)
            {
                cout<<"3";
                minin=j;
                min=(*j)->length+A[((*j)->tail)->c];
            }

        }

    }
    X.push_back((*minin)->head);
    A[((*minin)->tail)->c]=min;
    cout<<((*minin)->head)->value;

}

程序returns 出现段错误。我使用了各种 cout 语句来检查故障发生的位置，但控制台中没有打印任何内容。但是，我可以在控制台中输入边长，但输入后会直接出现分段错误。

Answer 1

在

a.push_back(&q);

您正在存储一个本地对象的地址，该对象将在函数终止后不复存在。

Answer 2

你为什么要创建一个 class 来保持你的 vertices/nodes？。我认为你应该使用从 0 到 N - 1 的纯整数以避免让事情变得更复杂。如果顶点由字符串或其他东西标识，您可以使用 hash/map 数据结构将键转换为整数。这将帮助您避免移动复杂的顶点结构和使用指针。

边缘 class 看起来不错，因为 Dijkstra 的算法需要所有数据才能工作（开始、结束顶点和路径的 weight/cost）。

话虽如此，该算法可以使用二叉堆数据结构来实现边选择的优先级。如果您不想实现二叉堆，您也可以使用优先级队列 (http://en.cppreference.com/w/cpp/container/priority_queue)。

最后，我将使用边向量迭代每个顶点的相邻顶点。

Dijkstra 算法中的分段错误

Segmentation fault in dijkstra's algorithm

c++

algorithm

dijkstra