Applying Dijkastra's algorithm on a graph of five nodes

Question

Last week I posted a piece of code to apply Dijkastra algorithm to calculate the shortest path between to nodes in a graph. Now, I've made some improvements, but I am still having difficulties.

I have a class Graph that is going to be constructed by two other classes. A vector of elements are instances of a class Edge, and another vector of elements of class Vertex. Every vertex has an id and a carried to keep the accumulated distance from the source node, and every edge has two vertices and weight.

Class Graph has a method named shortest and takes two vertices as arguments. The first one is for the source of the graph and the second is for the destination.

My approach is to eliminate the edges that are connected to the source vertex. This is done by adding their weights to the adjacent vertices, and saving them in "carried" which is in class Vertex. There is a field to keep tracking the situation of every vertex, which then goes to the next round, selecting the lowest vertex base on its carried to be a new source, while doing the same operation over and over until we end up with just one edge.

To demonstrate the result, I've initialized a graph with five vertices: vers[0], vers[1], vers[2], vers[3], vers[4]. There are 10 edges connecting those vertices starting from eds[0], eds[1], ....eds[9].

The destination vertex is vers[4] while the source vertex is vers[2]. It is connected by 4 edges, so when applying the method shortest as it is shown in the code below, I should get rid of all those 4 edges and end with 6 edges at the end of the first round.

The results as follows:

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

The result looks good so far because we don't see the the source vertex, which is 2, and we remained with just 6 edges after eliminating the four edges connected to the source vertex. We have to the right-hand side the weight of every edge, and down we have the carried of each remained vertex.

Now if we apply the second round, we get the following results:

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

We have 3 edges remained (which is correct) and three vertices (also correct), and the weights of edges are correct. But the problem is that I have the wrong "carried" for each vertex, and that will cause the code to select a wrong new source to continue in the following rounds (we should have 5, 2, 4 instead of 9, 2, 8).

I can see where is the problem, but I cannot understand why I am not getting the right solution when modifying the code. I think that the problem is located between the asterisks lines shown in the code.

#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
     vector<unsigned int> previous_nodes;    
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;};
    void previous_nodes_update(unsigned int val){previous_nodes.push_back(val);};
    void previous_nodes_erase(unsigned int val){previous_nodes.erase(previous_nodes.begin() + val);};
    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();) { // 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_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].get_id() == ver_out[iii].get_id()){vertices[i].set_carried(ver_out[iii].get_carried());};};


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

        track.clear();  

        if(ver_out[0].get_id() != dis.get_id()) {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].get_id() != dis.get_id()))
                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(); ) //++k)
                {
                    if((edges[k].get_ver_1().get_id() == src.get_id()) || (edges[k].get_ver_2().get_id() == src.get_id()))
                        {
                        track.push_back (edges[k]);
                        for(unsigned int i = 0; i < vertices.size(); ++i)
                        {
                        if(track.back().get_ver_1().get_id() == vertices[i].get_id()) edges[k].get_ver_1().set_carried(vertices[i].get_carried());
                        if(track.back().get_ver_2().get_id() == vertices[i].get_id()) edges[k].get_ver_2().set_carried(vertices[i].get_carried());
                        }

                        if(track.back().get_ver_1().get_id() == src.get_id())               
                            {
                            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].get_id() == src.get_id()) vertices.erase(vertices.begin() + t);

            track.clear();


            if(ver_out[0].get_id() != dis.get_id()) {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().get_id() == dis.get_id()) 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;
}

*edition was added so now it is same code but with some editions ****

I have added the == operator to the class Vertex and tried to get rid of every call to get_id() method when it was used in comparison operation , as200_successsuggested earlier.

#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
     vector<unsigned int> previous_nodes;    
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;
}

Answer 1

According to the rules of this site, we don't fix non-working code. However, I think that this question deserves a response anyway, since problems with your programming style are a major impediment to reaching a solution. To be frank, the snippet you emphasized looks overwhelming.

You want to push as much complexity out of the algorithm as possible by making Edge and Vertex work better. One obvious simplification is to override Vertex.operator==(const Vertex &v) so that you don't have to call .get_id() everywhere.

You frequently iterate over all vertices in the graph and all edges in the graph to find objects that you care about. That makes your code cumbersome to read, and it will also hurt performance. Currently, your vertices and edges basically exist in isolation. When you construct your Graph, you should interpret the data into a more useful form by linking up the vertices and edges.

Compare your code against a what Dijkstra's algorithm is supposed to look like. Right now, I don't see much resemblance. Taking line 16 of the pseudocode, for example (for each neighbor v of u), you should take the hint to implement a Vertex.neighbor_iterator() or something similar.