1

上周我发布了一个代码来使用 Dijkastra 算法计算图中的最短路径,但它很长,没有人对完全阅读它感兴趣,所以我删除了它,现在我试图通过部分来简化代码,代码还没有完成,我将在这里剪掉部分代码,专注于我目前面临的第一个问题。

简而言之,我有一个类 Graph 它将由另外两个类构造一个元素向量是 Edge 类的实例,另一个是 Vertex 类元素的向量,每个顶点都有一个 id,每个边都有两个顶点和权重.

类 Graph 有一个方法,它的名字是最短的,它接受两个顶点作为参数,第一个用于图的源,第二个用于目的地。

到目前为止,我正在尝试消除连接到源顶点的边,但是我仍然在连接到源的向量边中得到了一个额外的边,而与源相关的所有其他边都被删除了。

为了演示结果,我初始化了一个图,它有五个顶点 vers[0]、vers[1]、vers[2]、vers[3]、vers[4],并且从 eds[0 开始有 10 条边连接这些顶点], eds[1], ....eds[9]。

源顶点是 vers[2] 由 4 条边连接,因此当应用最短的方法时,如下面的代码所示,我应该摆脱所有这 4 条边并以 6 条边结束,但结果是我得到了去掉 3 条边,剩下 7 条边,结果如下:

Hello, This is a graph
0____1     5
0____3     4
0____4     6
1____3     5
1____4     7
2____4     8
3____4     3
size of edges 7
size of vertices 5

如您所见,仍然有一条边连接到源 2 ,问题出在这条边上(顺便说一下 8 是边的权重)

2____4     8

最短的方法有问题,特别是在 for 循环中,我希望你能帮助找出我的错误。

提前致谢。这是代码

#include<iostream>
#include<vector>
#include <stdlib.h>   // for rand()
using namespace std;

const unsigned int N = 5;

class Vertex
{
 private:
     unsigned int id;                 // the name of the vertex  
public:   
    unsigned int get_id(){return id;};
    void set_id(unsigned int value) {id = value;};

    Vertex(unsigned int init_val = 0) :id (init_val){}      // constructor   
    ~Vertex() {};                                           // destructor
};


class Edge
{
  private:
    Vertex first_vertex;                 // a vertex on one side of the edge
    Vertex second_vertex;                // a vertex on the other side of the edge
    unsigned int weight;                 // the value of the edge ( or its weight )     
  public:   
    unsigned int get_weight() {return weight;};
    void set_weight(unsigned int value) {weight = value;};

    Vertex get_ver_1(){return first_vertex;};
    Vertex get_ver_2(){return second_vertex;};

    void set_first_vertex(Vertex v1) {first_vertex = v1;};
    void set_second_vertex(Vertex v2) {second_vertex = v2;};


    Edge(const Vertex& vertex_1 = 0, const Vertex& vertex_2 = 0, unsigned int init_weight = 0)
    : first_vertex(vertex_1), second_vertex(vertex_2), weight(init_weight)
     {
     }  


    ~Edge() {} ; // destructor

};


class Graph
{
private:
     std::vector<Vertex>   vertices;
     std::vector<Edge>   edges;  


public:
     Graph(vector<Vertex> ver_vector, vector<Edge> edg_vector)
    : vertices(ver_vector), edges(edg_vector){}

     ~Graph() {}

     vector<Vertex> get_vertices(){return vertices;}
     vector<Edge> get_edges(){return edges;}

     void set_vertices(vector<Vertex> vector_value) {vertices = vector_value;}
     void set_edges(vector<Edge> vector_ed_value) {edges = vector_ed_value;}

     unsigned int shortest(Vertex src, Vertex dis);


};



unsigned int Graph::shortest(Vertex src, Vertex dis) {
        vector<Vertex> ver_out;
        vector<Edge> track;

        for(unsigned int i = 0; i < edges.size(); ++i)
            {
                if((edges[i].get_ver_1().get_id() == src.get_id()) || (edges[i].get_ver_2().get_id() == src.get_id()))
                    {
                    track.push_back (edges[i]);

                    if(edges[i].get_ver_1().get_id() == src.get_id())
                        {ver_out.push_back (edges[i].get_ver_1());}
                    else
                        {ver_out.push_back (edges[i].get_ver_2());}

                    edges.erase(edges.begin() + i ); //****
                    }
            };


    }





int main()
{
cout<< "Hello, This is a graph"<< endl;

vector<Vertex> vers(5);
vers[0].set_id(0);
vers[1].set_id(1);
vers[2].set_id(2);
vers[3].set_id(3);
vers[4].set_id(4);

vector<Edge> eds(10);
eds[0].set_first_vertex(vers[0]);
eds[0].set_second_vertex(vers[1]);
eds[0].set_weight(5);   

eds[1].set_first_vertex(vers[0]);
eds[1].set_second_vertex(vers[2]);
eds[1].set_weight(9);

eds[2].set_first_vertex(vers[0]);
eds[2].set_second_vertex(vers[3]);
eds[2].set_weight(4);

eds[3].set_first_vertex(vers[0]);
eds[3].set_second_vertex(vers[4]);
eds[3].set_weight(6);

eds[4].set_first_vertex(vers[1]);
eds[4].set_second_vertex(vers[2]);
eds[4].set_weight(2);

eds[5].set_first_vertex(vers[1]);
eds[5].set_second_vertex(vers[3]);
eds[5].set_weight(5);

eds[6].set_first_vertex(vers[1]);
eds[6].set_second_vertex(vers[4]);
eds[6].set_weight(7);

eds[7].set_first_vertex(vers[2]);
eds[7].set_second_vertex(vers[3]);
eds[7].set_weight(1);

eds[8].set_first_vertex(vers[2]);
eds[8].set_second_vertex(vers[4]);
eds[8].set_weight(8);

eds[9].set_first_vertex(vers[3]);
eds[9].set_second_vertex(vers[4]);
eds[9].set_weight(3);


unsigned int path;

Graph graf(vers, eds);
path = graf.shortest(vers[2], vers[4]);


cout<<graf.get_edges()[0].get_ver_1().get_id() <<"____"<<graf.get_edges()[0].get_ver_2().get_id() <<"     "<<graf.get_edges()[0].get_weight()<< endl;  //test
cout<<graf.get_edges()[1].get_ver_1().get_id() <<"____"<<graf.get_edges()[1].get_ver_2().get_id() <<"     "<<graf.get_edges()[1].get_weight()<< endl;  //test
cout<<graf.get_edges()[2].get_ver_1().get_id() <<"____"<<graf.get_edges()[2].get_ver_2().get_id() <<"     "<<graf.get_edges()[2].get_weight()<< endl;  //test
cout<<graf.get_edges()[3].get_ver_1().get_id() <<"____"<<graf.get_edges()[3].get_ver_2().get_id() <<"     "<<graf.get_edges()[3].get_weight()<< endl;  //test
cout<<graf.get_edges()[4].get_ver_1().get_id() <<"____"<<graf.get_edges()[4].get_ver_2().get_id() <<"     "<<graf.get_edges()[4].get_weight()<< endl;  //test
cout<<graf.get_edges()[5].get_ver_1().get_id() <<"____"<<graf.get_edges()[5].get_ver_2().get_id() <<"     "<<graf.get_edges()[5].get_weight()<< endl;  //test
cout<<graf.get_edges()[6].get_ver_1().get_id() <<"____"<<graf.get_edges()[6].get_ver_2().get_id() <<"     "<<graf.get_edges()[6].get_weight()<< endl;  //test
//cout<<graf.get_edges()[7].get_ver_1().get_id() <<"____"<<graf.get_edges()[7].get_ver_2().get_id() <<"     "<<graf.get_edges()[7].get_weight()<< endl;  //test
//cout<<graf.get_edges()[8].get_ver_1().get_id() <<"____"<<graf.get_edges()[8].get_ver_2().get_id() <<"     "<<graf.get_edges()[8].get_weight()<< endl;  //test
//cout<<graf.get_edges()[9].get_ver_1().get_id() <<"____"<<graf.get_edges()[9].get_ver_2().get_id() <<"     "<<graf.get_edges()[9].get_weight()<< endl;  //test


cout<<"size of edges"<<graf.get_edges().size()<< endl;
cout<<"size of vertices"<<graf.get_vertices().size()<< endl;

return 0;
}
4

1 回答 1

1

这是因为您在 for 循环中有效地跳过了一些向量元素,因为即使在当前元素时Graph::shortest您也在递增。将其更改为以下内容以解决问题:ierase

for (unsigned int i = 0; i < edges.size();) { // no ++i here
    if ((edges[i].get_ver_1().get_id() == src.get_id()) || (edges[i].get_ver_2().get_id() == src.get_id())) {
        track.push_back(edges[i]);

        if (edges[i].get_ver_1().get_id() == src.get_id()) {
            ver_out.push_back(edges[i].get_ver_1());
        } else {
            ver_out.push_back(edges[i].get_ver_2());
        }

        edges.erase(edges.begin() + i);
    } else {
        ++i; // increment only if not erasing
    }
}

或者根据评论,使用迭代器:

for (auto i = edges.begin(); i != edges.end();) {
    if ((i->get_ver_1().get_id() == src.get_id()) || (i->get_ver_2().get_id() == src.get_id())) {
        track.push_back(*i);

        if (i->get_ver_1().get_id() == src.get_id()) {
            ver_out.push_back(i->get_ver_1());
        } else {
            ver_out.push_back(i->get_ver_2());
        }

        i = edges.erase(i);
    } else {
        i++;
    }
}

您还缺少return该函数中的语句。

于 2013-11-11T18:25:45.747 回答