Applying Dijkstra's algorithm on a graph of five nodes

Question

Last week, I posted a piece of code to apply Dijkstra's algorithm to calculate the shortest path between to nodes in a graph. I've made some improvements but still stuck.

I have a class Graph. It shall be constructed by two other classes: a vector of 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 a weight.

Class Graph has a method; its name is shortest and it takes two vertices as arguments: the first one is the source of the graph and the second is for the destination.

My approach is trying to eliminate the edges that are connected to the source vertex, and adding their weights to the adjacent vertices, saving them in carried, a field in Vertex to keep tracking the situation of every vertex. Then we'd select the lowest vertex base on its carried to be a new source and repeat the same operation over and over till we end up with just one edge.

To demonstrate the result, I initialized a graph which has five vertices vers[0], vers[1], vers[2], vers[3], vers[4], and 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 vers[2] is connected by 4 edges, so when applying the method shortest, as is shown in the code below, I should get rid of all 4 of those edges and end up with 6 edges at the end of the first round. The result is 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 

As we can see that the result looks good so far because we don't see the the source vertex which is 2 and we ended up with just 6 edges after eliminating the four edges connected to the source vertex. Plus we have to do the right hand side, or the weight of every edge, and down we have the carried of each remaining vertex.

Now if we do the second round, we get the following result:

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

As you can see we got 3 edges left (which is correct) and three vertices (also correct), and the weights of the edges are correct, but the problem is that I got incorrect carried values for each vertex and that will make the code select a wrong source to continue with in following rounds. Namely, we should have 5, 2, 4 instead of 9, 2, 8.

I can see where the problem is but I don't understand why I am not getting the right solution. I think the problem is located between the asterisked lines shown in the code.

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

As far as I understand your code, it lacks a few essential parts of Dijkstra's algorithm. Look at dijkstra on wikipedia to see all steps of the algorithm. Two things I can't find in your algorithm but that are definitely part of Dijkstra's algorithm:

1. Assigning an infinite (very high) initial distance (in your case carried) to every vertex
2. The total distance to every newly reached vertex is the weight/length of the edge leading to it + the distance of the other vertex to the source

I will include a working Dijkstra algorithm, so you have something to compare your own algorithm with. It includes some more advanced data structures (e.g. priority queue) but you will encounter that sooner or later anyway. Good luck learning and correcting!

#define MAX_VER 1000 // Maximum number of vertices
#define INFINITE 0x3fffffff // 7*f ~ 1.000.000.000

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

struct edge {
    int to;
    int length;
    edge(int to, int length) : to(to), length(length) {}
};

struct vertex {
    vector<edge> edges;
    int dis;
    int prev;
};

vertex vertices[MAX_VER];

void reset() {
    for (int i=0; i < MAX_VER; i++) {
        vertices[i].edges.clear();
        vertices[i].dis = INFINITE;
        vertices[i].prev = -1;
    }
}

void addedge(int from, int to, int length=-1, bool directed=true) {
    vertices[from].edges.push_back(edge(to, length));
    if (!directed) vertices[to].edges.push_back(edge(from, length));
}

typedef pair<int, int> pp;
void dijkstra(int source) {
    //distance, vertex
    priority_queue<pp, vector<pp>, greater<pp> > q;
    vertices[source].dis = 0;
    q.push(make_pair(0, source));
    while (!q.empty()) {
        int u = q.top().second;
        int dis = q.top().first;
        q.pop();
        if (dis > vertices[u].dis) continue;
        for (size_t i = 0; i < vertices[u].edges.size(); i++) {
            edge &e = vertices[u].edges[i];
            if (dis + e.length < vertices[e.to].dis) {
                vertices[e.to].dis = dis + e.length;
                vertices[e.to].prev = u;
                q.push(make_pair(vertices[e.to].dis, e.to));
            }
        }
    }
}

int main() {
    reset();
    addedge(0, 1, 5, false);
    addedge(0, 2, 9, false);
    addedge(0, 3, 4, false);
    addedge(0, 4, 6, false);
    addedge(1, 2, 2, false);
    addedge(1, 3, 5, false);
    addedge(1, 4, 7, false);
    addedge(2, 3, 1, false);
    addedge(2, 4, 8, false);
    addedge(3, 4, 3, false);

    dijkstra(2);
    cout << "Distance from vertex 2 to 4 is: " << vertices[4].dis << endl;
    return 0;
}