1

先週、ダイクストラのアルゴリズムを適用してグラフ内のノード間の最短経路を計算するコードを投稿しました。私はいくつかの改善を行いましたが、まだ立ち往生しています。

クラスがありGraphます。Edgeこれは、クラスのインスタンスのベクトルと、クラスの要素の別のベクトルの2 つの他のクラスによって構築されますVertex。carriedすべての頂点には、ソース ノードからの累積距離を保持するためのID と aがあり、すべてのエッジには 2 つの頂点と重みがあります。

クラスGraphにはメソッドがあります。その名前はshortestで、2 つの頂点を引数として取ります。1 つ目はグラフのソースで、2 つ目は目的地です。

私のアプローチは、ソース頂点に接続されているエッジを排除しようとし、それらの重みを隣接する頂点に追加してcarried、フィールドに保存しVertex、すべての頂点の状況を追跡し続けることです。次に、その上にある最も低い頂点ベースをcarried新しいソースとして選択し、エッジが 1 つだけになるまで同じ操作を繰り返します。

結果を示すために、5 つの頂点を持つグラフを初期化し、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 であるソース頂点が表示されず、ソース頂点に接続された 4 つのエッジを削除した後、わずか 6 つのエッジで終わったため、結果はこれまでのところ良好に見えます。さらに、右側、つまりすべての辺の重みを計算する必要があり、下にはcarried残りの各頂点の重みがあります。

2 回目のラウンドを実行すると、次の結果が得られます。

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 つのエッジ (これは正しい) と 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

私があなたのコードを理解している限り、ダイクストラのアルゴリズムのいくつかの重要な部分が欠けています。ウィキペディアのダイクストラを見て、アルゴリズムのすべてのステップを確認してください。私はあなたのアルゴリズムで見つけることができませんが、それは間違いなくダイクストラのアルゴリズムの一部です:

  1. すべての頂点に無限の（非常に高い）初期距離（あなたの場合は運ばれる）を割り当てる
  2. 新しく到達したすべての頂点までの合計距離は、それにつながるエッジの重み/長さ + ソースまでの他の頂点の距離です。

動作するダイクストラ アルゴリズムを含めるので、独自のアルゴリズムと比較することができます。いくつかのより高度なデータ構造 (優先キューなど) が含まれていますが、遅かれ早かれそれに遭遇することになります。がんばって学習と修正を！

#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 に答える