This is relatively a long code,if you have the tolerance and the will to find out how to make this code work then take a look please, i will appreciate your feed back.
i have spent two days trying to come up with a code to represent a **graph** , then calculate the shortest path using dijkastra algorithm , but i am not able to get the right result , even the code runs without errors , but the result is not correct , always i am getting 0.
briefly,i have three classes , Vertex, Edge, **Graph** , the Vertex class represents the nodes in the **graph** and it has id and carried ( which carry the weight of the links connected to it while using dijkastra algorithm ) and a vector of the ids belong to other nodes the path will go through before arriving to the node itself , this vector is named previous_nodes.
the Edge class represents the edges in the **graph** it has two vertices ( one in each side ) and a wight ( the distance between the two vertices ).
the **Graph** class represents the **graph** , it has two vectors one is the vertices included in this **graph** , and the other is the edges included in the **graph**.
inside the class **Graph** there is a method its name shortest takes the sources node id and the destination and calculates the shortest path using dijkastra algorithm, and i think that it is the most important part of the code.
my **theory** about the code is that i will create two vectors one for the vertices in the **graph** i will name it vertices and another vector its name is ver_out it will include the vertices out of calculation in the **graph**, also i will have two vectors of type Edge , one its name edges for all the edges in the **graph** and the other its name is track to contain temporarily the edges linked to the temporarily source node in every round , after the calculation of every round the vector track will be cleared.
in main() i created five vertices and 10 edges to simulate a **graph** , the result of the shortest path supposedly to be 4 , but i am always getting 0 , that means i am having something wrong in my code , so if you are interesting in helping me find my mistake and how to make the code work , please take a look.
the way shortest work is as follow at the beginning all the edges will be included in the vector edges , we select the edges related to the source and put them in the vector track , then we iterate through track and add the wight of every edge to the vertex (node ) related to it ( not the source vertex ) , then after we clear track and remove the source vertex from the vector vertices and select a new source , and start over again select the edges related to the new source , put them in track , iterate over edges in tack , adding the weights to the corresponding vertices then remove this vertex from the vector vertices, and clear track , and select a new source , and so on .
here is 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(unsigned int src, unsigned int dis) {
vector<Vertex> ver_out;
vector<Edge> track;
for(unsigned int i = 0; i < edges.size(); ++i)
{
if((edges[i].get_ver_1().get_id() == vertices[src].get_id()) || (edges[i].get_ver_2().get_id() == vertices[src].get_id()))
{
track.push_back (edges[i]);
edges.erase(edges.begin()+i);
}
};
for(unsigned int i = 0; i < track.size(); ++i)
{
if(track[i].get_ver_1().get_id() != vertices[src].get_id())
{
track[i].get_ver_1().set_carried((track[i].get_weight()) + track[i].get_ver_2().get_carried());
track[i].get_ver_1().previous_nodes_update(vertices[src].get_id());
}
else
{
track[i].get_ver_2().set_carried((track[i].get_weight()) + track[i].get_ver_1().get_carried());
track[i].get_ver_2().previous_nodes_update(vertices[src].get_id());
}
}
for(unsigned int i = 0; i < vertices.size(); ++i)
if(vertices[i].get_id() == src) vertices.erase(vertices.begin() + i); // removing the sources vertex from the vertices vector
ver_out.push_back (vertices[src]);
track.clear();
if(vertices[0].get_id() != dis) {src = vertices[0].get_id();}
else {src = vertices[1].get_id();}
for(unsigned int i = 0; i < vertices.size(); ++i)
if((vertices[i].get_carried() < vertices[src].get_carried()) && (vertices[i].get_id() != dis))
src = vertices[i].get_id();
//while(!edges.empty())
for(unsigned int round = 0; round < vertices.size(); ++round)
{
for(unsigned int k = 0; k < edges.size(); ++k)
{
if((edges[k].get_ver_1().get_id() == vertices[src].get_id()) || (edges[k].get_ver_2().get_id() == vertices[src].get_id()))
{
track.push_back (edges[k]);
edges.erase(edges.begin()+k);
}
};
for(unsigned int n = 0; n < track.size(); ++n)
if((track[n].get_ver_1().get_id() != vertices[src].get_id()) && (track[n].get_ver_1().get_carried() > (track[n].get_ver_2().get_carried() + track[n].get_weight())))
{
track[n].get_ver_1().set_carried((track[n].get_weight()) + track[n].get_ver_2().get_carried());
track[n].get_ver_1().previous_nodes_update(vertices[src].get_id());
}
else if(track[n].get_ver_2().get_carried() > (track[n].get_ver_1().get_carried() + track[n].get_weight()))
{
track[n].get_ver_2().set_carried((track[n].get_weight()) + track[n].get_ver_1().get_carried());
track[n].get_ver_2().previous_nodes_update(vertices[src].get_id());
}
for(unsigned int t = 0; t < vertices.size(); ++t)
if(vertices[t].get_id() == src) vertices.erase(vertices.begin() + t);
track.clear();
if(vertices[0].get_id() != dis) {src = vertices[0].get_id();}
else {src = vertices[1].get_id();}
for(unsigned int tt = 0; tt < edges.size(); ++tt)
{
if(vertices[tt].get_carried() < vertices[src].get_carried())
{
src = vertices[tt].get_id();
}
}
}
return vertices[dis].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(2, 4);
cout<< path << endl;
return 0;
}