Last week I posted a piece of code to apply Dijkstra's algorithm to calculate the shortest path between two 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; every edge has two vertices and a weight.

Class Graph has a method named shortest() which 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 remaining (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 <stdlib.h>   // for rand()
using namespace std;

class Vertex
     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;    
    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
    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 )     
    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
     std::vector<Vertex>   vertices;
     std::vector<Edge>   edges;  

     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)) {

                if (edges[i].get_ver_1() == src) {
                } else {

                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);
        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];
        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());
                            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);
                            ++k; // increment only if not erasing
            for(unsigned int t = 0; t < vertices.size(); ++t)
                if(vertices[t] == src) vertices.erase(vertices.begin() + t);

            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];
        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);

vector<Edge> eds(10);










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;

1 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.

  • \$\begingroup\$ the first point you have mentioned is very important , actually i am very new to C++ and even i thought about operators overriding but i was wondering on the real reason why the code is not producing the correct result, now i am going to work on defining the operators overriding trying to simplifying the complexity of the code.Thanks a lot (i wanted to vote up but i have not enough reputations), i hope i can find the bug of this code , my wonder is why it is not working more than Dijkastra algorithm itself as a learner of C++. \$\endgroup\$
    – mazen.r.f
    Commented Nov 13, 2013 at 19:56
  • \$\begingroup\$ i added the operator == to the class Vertex , and edited the code to get rid of many calls to get_id(). Once again thank you 200_success \$\endgroup\$
    – mazen.r.f
    Commented Nov 13, 2013 at 21:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.