# Applying Dijkastra's algorithm on a graph of five nodes

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;
}