This is relatively long code. Please take a look at this code if you are still willing to do so. I will appreciate your feedback.
I have spent two days trying to come up with code to represent a graph, calculating the shortest path using Dijkstra's algorithm. But I am not able to get the right result, even though the code runs without errors. The result is not correct and I am always getting 0.
I have three classes: Vertex, Edge, and 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 Dijkstra's 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 and has two vertices (one in each side) and a width (the distance between the two vertices).
The Graph class represents the graph. It has two vectors, where 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 named shortest() that takes the sources node id and the destination and calculates the shortest path using Dijkstra's algorithm. 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 named vertices, and another vector named ver_out (it will include the vertices out of calculation in the graph). I will also have two vectors of type Edge, where one is named edges (for all the edges in the graph), and the other is named track (to temporarily contain the edges linked to the temporary source node in every round). After the calculation of every round, the vector track will be cleared.
In main(), I've created five vertices and 10 edges to simulate a graph. The result of the shortest path supposedly is 4, but I am always getting 0. That means I have something wrong in my code. If you are interesting in helping me find my mistake and making 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 width of every edge to the vertex (node) related to it (not the source vertex). After that, we clear track and remove the source vertex from the vector vertices and select a new source. Then we start over again and select the edges related to the new source, put them in track, iterate over edges in track, adding the weights to the corresponding vertices, then remove this vertex from the vector vertices. Then clear track, and select a new source, and so on.
#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;
}
