上周我发布了一个代码来使用 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;
}