1

上周，我发布了一段代码来应用 Dijkstra 算法来计算图中节点之间的最短路径。我做了一些改进，但仍然卡住了。

我有一堂课Graph。它应该由另外两个类构成：一个类的实例Edge向量和另一个类元素的向量Vertex。每个顶点都有一个 ID 和 acarried以保持与源节点的累积距离，每条边都有两个顶点和一个权重。

类Graph有方法；它的名字是shortest，它接受两个顶点作为参数：第一个是图的源，第二个是目的地。

我的方法是尝试消除连接到源顶点的边，并将它们的权重添加到相邻顶点，将它们保存在 中carried，Vertex以保持跟踪每个顶点的情况。然后我们会选择它的最低顶点carried作为新源，并一遍又一遍地重复相同的操作，直到我们最终只有一条边。

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

目标顶点是vers[4]源顶点vers[2]由 4 条边连接时，所以在应用方法时shortest，如下面的代码所示，我应该去掉所有 4 条边，并在第一个边的末尾有 6 条边圆形的。结果如下：

Hello, This is a graph
0____1     5
0____3     4
0____4     6
1____3     5
1____4     7
3____4     3
size of edges  6
size of vertices  4
curried vertex_0  9
curried vertex_1  2
curried vertex_2  1
curried vertex_3  8

正如我们所看到的，到目前为止结果看起来不错，因为我们没有看到源顶点 2，并且在消除了连接到源顶点的四个边之后，我们最终只有 6 个边。另外，我们必须做右手边，或每条边的权重，向下我们有carried每个剩余顶点的权重。

现在，如果我们进行第二轮，我们会得到以下结果：

Hello, This is a graph
0____1     5
0____4     6
1____4     7
size of edges  3
size of vertices  3
curried vertex_0  9
curried vertex_1  2
curried vertex_2  8

正如你所看到的，我们剩下 3 个边（这是正确的）和三个顶点（也是正确的），边的权重是正确的，但问题是我carried为每个顶点得到了不正确的值，这将使代码选择在接下来的几轮中继续使用错误的来源。即，我们应该有5, 2, 4而不是9, 2, 8.

我可以看到问题出在哪里，但我不明白为什么我没有得到正确的解决方案。我认为问题位于代码中显示的星号行之间。

这是代码：

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


class Vertex
{
 private:
     unsigned int id;                 // the name of the vertex
     unsigned int carried;            // the weight a vertex may carry when calculating shortest path    
public:   
    unsigned int get_id(){return id;};
    unsigned int get_carried(){return carried;};
    void set_id(unsigned int value) {id = value;};
    void set_carried(unsigned int value) {carried = value;};
    inline bool operator==( const Vertex& ver_1){ return id == ver_1.id;};
    Vertex(unsigned int init_val = 0, unsigned int init_carried = 0) :id (init_val), carried(init_carried)     // 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();) { 
            if ((edges[i].get_ver_1() == src) || (edges[i].get_ver_2() == src)) {
                track.push_back(edges[i]);

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

                }

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

        for(unsigned int i = 0; i < vertices.size(); ++i)  
            for(unsigned int iii = 0; iii < ver_out.size(); ++iii) {
                if(vertices[i] == ver_out[iii]){vertices[i].set_carried(ver_out[iii].get_carried());};};


        for(unsigned int i = 0; i < vertices.size(); ++i)
            if(vertices[i] == src) vertices.erase(vertices.begin() + i);

        track.clear();  

        if(!(ver_out[0] == dis)) {src = ver_out[0];}
        else {src = ver_out[1];}

        for(unsigned int i = 0; i < ver_out.size(); ++i)          
            if((ver_out[i].get_carried() < src.get_carried()) && (!(ver_out[i] == dis)))
                src = ver_out[i];

        ver_out.clear();


        for(unsigned int round = 0; round < 1 ; ++round)     //vertices.size()
        {
            for(unsigned int k = 0; k < edges.size(); ) 
                {
                    if((edges[k].get_ver_1() == src) || (edges[k].get_ver_2() == src))
                        {
                        track.push_back (edges[k]);
                        for(unsigned int i = 0; i < vertices.size(); ++i)
                        {
                        if(track.back().get_ver_1() == vertices[i]) edges[k].get_ver_1().set_carried(vertices[i].get_carried());
                        if(track.back().get_ver_2() == vertices[i]) edges[k].get_ver_2().set_carried(vertices[i].get_carried());
                        }

                        if(track.back().get_ver_1() == src)             
                            {
                            ver_out.push_back (track.back().get_ver_2()); //************************************ 
                            if(track.back().get_ver_2().get_carried() > (track.back().get_ver_1().get_carried() + track.back().get_weight())) //<===
                                ver_out.back().set_carried(track.back().get_ver_1().get_carried() + track.back().get_weight());
                            else ver_out.back().set_carried(track.back().get_ver_2().get_carried());

                            }
                        else{
                            ver_out.push_back (track.back().get_ver_1());
                            if(track.back().get_ver_1().get_carried() > (track.back().get_ver_2().get_carried() + track.back().get_weight())) // <===
                                ver_out.back().set_carried(track.back().get_ver_2().get_carried() + track.back().get_weight());
                            else {ver_out.back().set_carried(track.back().get_ver_1().get_carried());}
                            }
                            //*****************************
                        edges.erase(edges.begin() + k);
                        }
                    else{
                            ++k; // increment only if not erasing
                        }
                };


            for(unsigned int t = 0; t < vertices.size(); ++t)
                if(vertices[t] == src) vertices.erase(vertices.begin() + t);

            track.clear();


            if(!(ver_out[0] == dis)) {src = ver_out[0];}
            else {src = ver_out[1];}

            for(unsigned int tt = 0; tt < edges.size(); ++tt)
                {
                if(ver_out[tt].get_carried() < src.get_carried())
                    {
                    src = ver_out[tt];
                    }
                }
            ver_out.clear();
        }
        if(edges[0].get_ver_1() == dis) return edges[0].get_weight() +edges[0].get_ver_2().get_carried();
        else return edges[0].get_weight() +edges[0].get_ver_1().get_carried();

    }






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;
cout<<"curried vertex_0  "<<graf.get_vertices()[0].get_carried()<< endl;
cout<<"curried vertex_1  "<<graf.get_vertices()[1].get_carried()<< endl;
cout<<"curried vertex_2  "<<graf.get_vertices()[2].get_carried()<< endl;
//cout<<"curried vertex_3  "<<graf.get_vertices()[3].get_carried()<< endl;
//cout<< path << endl;

return 0;
}
4

1 回答 1

3

据我了解您的代码，它缺少 Dijkstra 算法的一些基本部分。查看wikipedia 上的 dijkstra以查看算法的所有步骤。我在您的算法中找不到两件事，但这绝对是 Dijkstra 算法的一部分：

  1. 为每个顶点分配一个无限（非常高）的初始距离（在您的情况下）
  2. 到每个新到达的顶点的总距离是通向它的边的权重/长度 + 另一个顶点到源的距离

我将包含一个有效的 Dijkstra 算法，因此您可以将自己的算法与之进行比较。它包括一些更高级的数据结构（例如优先级队列），但无论如何你迟早会遇到。祝您学习和纠正好运！

#define MAX_VER 1000 // Maximum number of vertices
#define INFINITE 0x3fffffff // 7*f ~ 1.000.000.000

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct edge {
    int to;
    int length;
    edge(int to, int length) : to(to), length(length) {}
};

struct vertex {
    vector<edge> edges;
    int dis;
    int prev;
};

vertex vertices[MAX_VER];

void reset() {
    for (int i=0; i < MAX_VER; i++) {
        vertices[i].edges.clear();
        vertices[i].dis = INFINITE;
        vertices[i].prev = -1;
    }
}

void addedge(int from, int to, int length=-1, bool directed=true) {
    vertices[from].edges.push_back(edge(to, length));
    if (!directed) vertices[to].edges.push_back(edge(from, length));
}

typedef pair<int, int> pp;
void dijkstra(int source) {
    //distance, vertex
    priority_queue<pp, vector<pp>, greater<pp> > q;
    vertices[source].dis = 0;
    q.push(make_pair(0, source));
    while (!q.empty()) {
        int u = q.top().second;
        int dis = q.top().first;
        q.pop();
        if (dis > vertices[u].dis) continue;
        for (size_t i = 0; i < vertices[u].edges.size(); i++) {
            edge &e = vertices[u].edges[i];
            if (dis + e.length < vertices[e.to].dis) {
                vertices[e.to].dis = dis + e.length;
                vertices[e.to].prev = u;
                q.push(make_pair(vertices[e.to].dis, e.to));
            }
        }
    }
}

int main() {
    reset();
    addedge(0, 1, 5, false);
    addedge(0, 2, 9, false);
    addedge(0, 3, 4, false);
    addedge(0, 4, 6, false);
    addedge(1, 2, 2, false);
    addedge(1, 3, 5, false);
    addedge(1, 4, 7, false);
    addedge(2, 3, 1, false);
    addedge(2, 4, 8, false);
    addedge(3, 4, 3, false);

    dijkstra(2);
    cout << "Distance from vertex 2 to 4 is: " << vertices[4].dis << endl;
    return 0;
}
于 2013-11-13T18:19:51.813 回答